


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
onedimensional 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 timestep, 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 timestep 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 6state minimal time solution which
is performed in 2n1 timesteps, where n is the number of Soldiers
in the line.
For further information
 J.Mazoyer. "A 6State Minimal Time Solution to the Firing
Squad Synchronization Problem". Theoretical Computer Science
50, 1987, pp. 183238.
Resources

End of task (final state reached).
© E.
Petraglio
1,308KB JPEG 

