Firing Squad
In this experiment, the BioWall solves the synchronization problem of any column of cells defined by the visitor. The solution implemented on the BioWall achieves synchronization in minimal time.

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.

Figure 1: The synchronization process of a vertical line of 10 Soldiers on the BioWall.

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
  • J.Mazoyer. "A 6-State Minimal Time Solution to the Firing Squad Synchronization Problem". Theoretical Computer Science 50, 1987, pp. 183-238.


End of task (final state reached).
© E. Petraglio

1,308KB JPEG