 |
|
|
|
 |
 |
||
 |
 |
 |
|
|
Firing Squad The implementation of the firing squad synchronization problem involves a uniform one-dimensional cellular automaton. The cells of the automaton are called Soldiers, with the General at one of the ends. The problem is to specify the states and transitions of the Soldiers in such a way that the General can cause all of them to go into a particular final state (i.e., they fire their guns) at the same time. At the beginning, all the Soldiers are assumed to be in a single state, the quiescent state. When the General undergoes the transition to the state labeled 'fire when ready', he does not take any initative afterwards, and the rest is up to the Soldiers. The signal can propagate down the line no faster than one Soldier per time-step, and their problem is how to get all coordinated and in rhythm. In the process, none of the Soldiers is permitted to count as high as the number of Soldiers in the firing squad.
Instructions for use In the BioWall implementation of the firing squad, you can first define a vertical line of idle Soldiers by simply pressing the membrane of adjacent units in a same column (Figure 1). When you touch again anyone of the idle Soldiers, all of them become active in yellow at once and the lower one changes to General in red. The successive states of the firing squad appear then one per time-step in the successive columns to the right. The process goes on until all the Soldiers reach simultaneously the green fire state. There are many solutions to the firing squad synchronization problem. The one implemented on the BioWall is a 6-state minimal time solution which is performed in 2n-1 time-steps, where n is the number of Soldiers in the line.
For further information
Resources
|
