Information Technology Reference
In-Depth Information
An E
cient Mapping Scheme for Embedding
Any One-Dimensional Firing Squad
Synchronization Algorithm onto
Two-Dimensional Arrays
Hiroshi Umeo, Masashi Maeda, and Norio Fujiwara
Osaka Electro-Communication University,
Neyagawa-shi, Hatsu-cho 18-8, Osaka, 572-8530, Japan
umeo@umeolab.osakac.ac.jp
Abstract.
An e
'
cient mapping scheme is proposed for embedding any
one-dimensional firing squad synchronization algorithm onto 2-D arrays,
and some new 2-D synchronization algorithms based on the mapping
scheme are presented. The proposed mapping scheme can be readily ap-
plied to the design of synchronization algorithms with fault tolerance,
algorithms operating on multi-dimensional cellular arrays, and for the
generalized case where the general is located at an arbitrary position on
the array. A six-state algorithm is developed that can synchronize any
m
×
n
rectangular array in 2(
m
+
n
)
−
4 steps. In addition, we develop
a nine-state optimum-time synchronization algorithm on square arrays.
We progressively reduce the number of internal states of each cellular
automaton on square and rectangular arrays, achieving nine states for a
square array and six states for a rectangular array. These are the small-
est number of states reported to date for synchronizing rectangular and
square arrays.
1 Introduction
The famous firing squad synchronization problem [13] is stated as follows: Given
an array of
n
identical cellular automata, including a
general
at the left end
that is activated at time
t
= 0, we want to design the automata such that,
at
some future time
, all the cells will
simultaneously
and,
for the first time
, enter
a special
firing
state. The problem was originally proposed by J. Myhill in 1957
to synchronize all parts of a self-reproducing machine, and it was subsequently
presented in detail by Moore [13] in 1964. The firing squad synchronization
problem has been studied extensively in more than forty years [1-25].
The present authors are involved in research on firing squad synchronization
algorithms on two-dimensional (2-D) cellular arrays. Several synchronization al-
gorithms on 2-D arrays have been proposed, including Grasselli [4], Kobayashi
[6], Shinahr [16] and Szwerinski [17]. To date, the smallest number of cell states
for which a synchronization algorithm has been developed is 17 for a square
array and 28 for rectangular array, achieved by Shinahr [16].
