An optimum solution to the firing squad synchronization problem. (English) Zbl 1111.68527

Waksman, Abraham

Inf. Control 9, 66-78 (1966).

Summary: A 16 state machine is proposed as an optimum solution to the ‘firing squad synchronization problem’. It is shown that when given an arbitrarily long (but finite) array of such machines and a command at one end at \(t=0\), it is possible to cause all the machines to go to one terminal state, all at once, at time \(t=2n-2\) where \(n\) is the number of machines in the array. The code book of the state transitions of the machine is so arranged as to cause the array to progressively divide itself into \(2^k\) equal parts, where \(k\) is an integer and an increasing function of time. The end machines in each partition assume a special state so that when the last partition occurs, all the machines have for both neighbors machines at this stage. This is made the only condition for any machine to assume terminal state.

MSC:

68Q80

Cellular automata (computational aspects)