Information Technology Reference
In-Depth Information
In this paper, we propose a simple and e
;
cient mapping scheme for em-
bedding any one-dimensional firing squad synchronization algorithm onto 2-D
arrays and present some new 2-D synchronization algorithms. The first 6-state
algorithm we develop can synchronize any
m×n
rectangular array in 2(
m
+
n
)
−
4
steps. Although the algorithm is min(
m, n
)
−
1 steps slower than the optimum
case, the number of internal states has been reduced considerably. Our map-
ping scheme can be easily applied to the design of synchronization algorithms
with fault-tolerance, for algorithms operating on multi-dimensional cellular ar-
rays, and for the generalized case where the general is located at any position
on the array. The proposed mapping scheme allows us to obtain the first fault-
tolerant synchronization algorithm on 2-D arrays. In addition, we develop a
9-state optimum-time synchronization algorithm on square arrays through pro-
gressive reduction of the number of internal states of each cellular automaton.
1
2
3
4
n
...
1
C
11
C
12
C
13
C
14
C
1
n
...
2
C
21
C
22
C
23
C
24
C
2
n
...
3
C
31
C
32
C
33
C
34
C
3
n
...
m
C
m
1
C
m
2
C
m
3
C
m
4
C
mn
Fig. 1.
Two-dimensional array of cellular automata
2 Firing Squad Synchronization Problem on
Two-Dimensional Arrays
Figure 1 shows a finite two-dimensional cellular array consisting of
m × n
cells.
Each cell is an identical (except the border cells) finite-state automaton. The
array operates in lock-step mode in such a way that the next state of each cell
(except border cells) is determined by both its own present state and the present
states of its north, south, east and west neighbors. All cells (
soldiers
), except the
north-west corner cell (
general
), are initially in the quiescent state at time
t
=0
with the property that the next state of a quiescent cell with quiescent neighbors
is the quiescent state again. At time
t
= 0, the north-west corner cell C
1
,
1
is in
the
fire-when-ready
state, which is the initiation signal for the array. The firing
squad synchronization problem is to determine a description (state set and next-
state function) for cells that ensures all cells enter the
fire
state at exactly the
