Information Technology Reference
In-Depth Information
In the long history of the study of the firing squad synchronization problem,
many optimum-time synchronization algorithms have been proposed, including
Balzer [1], Goto [3], Mazoyer [10] and Waksman [24]. The 6-state optimum-time
algorithm on 1-D arrays developed by Mazoyer [10] is the smallest number of
internal states for which such an algorithm has been developed. We can obtain a
6-state rectangular firing algorithm based on the 6-state Mazoyer's synchroniza-
tion algorithm through lemma 3 below. Our next rectangular synchronization
algorithm fires any
m×n
array in 2(
m
+
n
)
−
4 steps, and it is min(
m, n
)
−
1 steps
slower than the optimum 28-state algorithm given in Shinahr [16]. However, the
number of internal states is considerably smaller. In Fig. 4, we show snapshots
of our 6-state firing synchronization algorithm running on a rectangular array of
size 5
×
7.
[Lemma 3]
[10]
There exists a 6-state 1-D cellular automaton that can synchro-
nize
n
cells in the optimum 2
n −
2 steps.
[Theorem 4]
There exists a 6-state firing squad synchronization algorithm that
can synchronize any
m × n
rectangular array in 2(
m
+
n
)
−
4 steps.
Fig. 5.
A 2-D cellular array with faulty rectangular holes
4 Applications of the Mapping Scheme
Some applications and extensions of our mapping scheme are given below. The
first problem we consider is the design of a fault-tolerant synchronization algo-
rithm on 2-D arrays.
4.1 Fault-Tolerant Synchronization Algorithm on 2-D Arrays
A firing squad synchronization problem on 1-D arrays with faulty cells has been
studied by Kutrieb and Vollmar [7] and Umeo [18]. A similar problem on 2-D
arrays has never been discussed or studied due to the di
;
culties in designing
such synchronization algorithms. Here we present first a fault-tolerant synchro-
nization algorithm on 2-D arrays. The array we consider includes some faulty
regions, each consisting of faulty cells that cannot transmit any information or
change state. Each faulty region is rectangular, and isolated from each other and
