Firing squad synchronization problem
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 analagous to problems of logical design, systems design, and programming, and can be stated as follows:
- Consider a finite amount - but arbitrarily many - of identical finite state machines (soldiers) arranged in a line. At time , every automaton is initialized to the same state, except for the automaton on the far left (the general). At every time , the state of every automaton is dependent upon its state and the state of its two neighbors at time (except for the two automata at either end, whose state depends only upon itself and its one neighbor). In addition, each automaton cannot change state if its state and its neighbors' states at time is equal to the initial state. The problem is to define such a set of rules for the automata such that all automata enter for the first time a distinguished state (fire) at the same time.
History of the Problem
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 amount of states was introduced by Jacques Mazoyer in 1988, whose solution uses only six states. In addition, he also proved that no four state solution exists, although the existance of a five state solution is still unknown.
A solution using a minimal amount of time was later found by Professor E. Goto at M.I.T., whose solution uses thousands of states and requires exactly units of time for soldiers. It is proven that a solution using a smaller amount of time cannot exist.
General Solution
The 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 number of soldiers.
Generalizations
Several generalizations of the FSSP have been conjectured and studied, including the FSSP on one-dimensional lines with the general at an aribtrary location, closed rings, Cayley graphs, squares, rectangles, cubes, and general networks.