Firing squad synchronization problem

One solution to the FSSP using 15 states and 3n units of time.

The firing squad synchronization problem is a problem in computer science and cellular automata first proposed by John Myhill in 1957 and published (with a solution) in 1962 by Edward Moore. The problem is analogous to problems of logical design, systems design, and programming, and can be stated as follows:

Consider a finite but arbitrary number of identical finite state machines (soldiers) arranged in a line. At time t = 0, each soldier is initialized to the quiescent (idle) state, except for the soldier on the far left (the general). The state of each soldier at each discrete time-step t > 0 is dependent on its state and the state of its two neighbors at time t − 1 (except for the two soldiers at either end, each of whose state depends only on itself and its sole neighbor). In addition, if a soldier and its neighbors are in the quiescent state, then the soldier will remain quiescent at the next time-step. The problem is to define a finite set of states and state transition rules for the soldiers such that all soldiers enter a distinguished state (fire) at the same time and for the very first time.

History

The first solution to the FSSP was found by John McCarthy and Marvin Minsky and was published in Sequential Machines by Moore. A solution using a minimal number of states was introduced by Jacques Mazoyer in 1988, whose solution uses only six states.^[1] Robert Balzer had earlier proven that no four-state solution exists. Peter Sanders later found that Balzer's search procedure was incomplete, but managed to reaffirm the four-state non-existence result through a corrected search procedure. It is still unknown whether a five-state solution exists.

A solution using a minimal amount of time was later found by Professor E. Goto at MIT, whose solution uses thousands of states and requires exactly 2n − 2 units of time for n soldiers. It is proven that a solution using a smaller amount of time cannot exist.

General solution

A general solution to the FSSP involves propagating two waves down the line of soldiers: a fast wave and a slow wave moving three times as slow. The fast wave bounces off the other end of the line and meets the slow wave in the centre. The two waves then split into four waves, a fast and slow wave moving in either direction from the centre, effectively splitting the line into two equal parts. This process continues, subdividing the line until each division is of length 1. At this moment, every soldier fires. This solution requires 3n units of time for n soldiers.

A time-optimal solution for the line

A time-optimal solution was first described in (Waksman,1966). The general sends to the right signals $S_{1},S_{2},S_{3},\ldots ,S_{i}$ at speeds 1, 1/3, 1/7, ..., 1/(2ⁱ⁻¹ − 1). The signal $S_{1}$ reflects at the right end of the line (like the fast wave in the preceding section), and meets signal S_i (for i ≥ 2) at cell n/2ⁱ⁻¹. When S₁ reflects, it also creates a new general at the right end.

Signals S_i are constructed using auxiliary signals, which propagate to the left. Every second time a signal moves (to the right), it sends an auxiliary signal to the left. S₁ moves on its own at speed 1 while each of the slower signals moves only when it gets an auxiliary signal.

Generalizations

Several generalizations of the FSSP have been proposed and studied, including the FSSP on one-dimensional lines with the general at an arbitrary location, closed rings, Cayley graphs, squares, rectangles, cubes, and general networks.

External links

[1] "Firing Squad Problem"
[2] "On Formulations of Firing Squad Synchronization Problems"
[3] "Firing squad synchronization"

References

^ Mazoyer 1987

Waksman, Abraham (1966). "An Optimum Solution to the Firing Squad Synchronization Problem". Information and Control. 9 (1): 66–78. doi:10.1016/S0019-9958(66)90110-0. {{cite journal}}: More than one of |author= and |last= specified (help); Unknown parameter |month= ignored (help)

Mazoyer, Jacques (1987). "A six-state minimal time solution to the firing squad synchronization problem". Theoretical Computer Science. 50 (2): 183–238. doi:10.1016/0304-3975(87)90124-1.

Balzer, Robert (1967). "An 8-state Minimal Time Solution to the Firing Squad Synchronization Problem". Information and Control. 10 (1): 22–42. doi:10.1016/S0019-9958(67)90032-0. {{cite journal}}: External link in |bibsource= (help); Unknown parameter |bibsource= ignored (help); Unknown parameter |month= ignored (help)

Shinahr, Ilka (1974). "Two- and three-dimensional firing-squad synchronization problem". Information and Control. 24. Academic Press: 163–180. doi:10.1016/S0019-9958(74)80055-0. {{cite journal}}: Unknown parameter |address= ignored (|location= suggested) (help)

F. R. Moore and G. G. Langdon (1968). "A Generalized Firing Squad Problem". Information and Control. 12 (3): 212–220. {{cite journal}}: Unknown parameter |month= ignored (help); Unknown parameter |references= ignored (help)

[1] Mazoyer 1987

[1]