The Firing Squad Synchronization Problem

At time step 0, all cells are in the quiescent state. At some time step t = U, the general (responding to an external input) goes into a special state, interpreted as a command to fire. Then at some later time step = i/, all of the soldier cells must go into the firing state, and none of them can have been in the firing state at any previous time step. The problem is to devise states and state transitions for the soliders that will accomplish this behavior. 

It can be shown that the minimum possible time to fire is 2iV — 2. A solution achieving this minimal time was first proposed in an unpublished manuscript by E. Goto (Moore, 1964). The solution described above can be implemented with 15 states per cell (Fischer, 1965). A fair amount of research has gone into finding minimal-time solutions with a minimum number of states (e.g., Waksman, 1966 Balzer, 1967 Mazoyer, 1987 Yunes, 1994) and in finding solutions to generaliza- 

---

Fig. 4.9 Schematic illustration of one solution to the firing squad synchronization problem, adapted from Fischer (1965). Signal A (solid line) travels at velocity 1, and signal B (dashed line) travels at velocity 1/3. General cells contain black dots and boundary cells are shaded.

Balzar, R. (1967) An 8-states minimal time solution to the firing squad synchronization problem. Information and Control, 10, 22-42. 

Mazoyer, J. (1988) An overview of the firing squad synchronization problem. In C. Choffurt (editor), Automata Networks 82-93. Lecture Notes in Computer Science, Vol. 316. Springer-Verlag. 

Moore, E. F. (1964) The firing squad synchronization problem. In E. F. Moore (editor), Sequential Machines Selected Papers, 213-214. Reading, MA Addison-Wesley. 

Yunes, J. B. (1994) Seven-state solutions to the firing squad synchronization problem. Theoretical Computer Science, 127, 313-332,... 

---