Affiliations: Faculty of Information Science and Technology, Univ.
of Osaka Electro-Communication, Japan. E-mail:
{umeo,maedam,hisaoka,teraoka}@umeolab.osakac.ac.jp
Abstract: A simple and state-efficient mapping scheme is proposed for
embedding any one-dimensional (1-D) firing squad synchronization algorithm onto
two-dimensional (2-D) arrays, and some new 2-D synchronization algorithms based
on the mapping scheme are presented. The proposed mapping scheme can be readily
applied to the design of 2-D 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
2-D array. First a six-state algorithm is developed that can synchronize any
m×n rectangular array in 2(m+n)−4 steps. Then, a
fourteen-state generalized algorithm is also developed that can synchronize any
m×n rectangular array with the general at an arbitrary initial position
(r,s) in m+n+max(r+s,m+n−r−s+2)−4
steps. The latter algorithm is interesting in that it includes a new
optimum-time synchronization algorithm as a special case where the general is
located at one corner. We progressively reduce the number of internal states of
each cellular automaton on rectangular arrays, achieving six states and
fourteen states for a rectangular array in non-optimum and optimum-time
complexities, respectively. These are the smallest number of states reported to
date for synchronizing rectangular arrays.
