An Optimum-Time Firing Squad Synchronization Algorithm for Two-Dimensional Rectangle Arrays:
Freezing-Thawing Technique Based
Hiroshi Umeo. Takuya Yamawaki and Kinuo Nishide
The firing squad synchronization problem on cellular automata has been studied extensively for more than fifty years, and a rich variety of synchronization algorithms have been proposed for not only one-dimensional but two-dimensional arrays. In the present paper, we propose a new optimum time synchronization algorithm that can synchronize any rectangle array of size m * n with a general at one corner in m + n + max (m, n) − 3 steps. The algorithm is based on a new, simple mapping scheme which embeds synchronization operations on one-dimensional arrays onto two dimensional arrays, utilizing a freezing-thawing technique. A proposed 124-state, 45128-rule implementation of the algorithm gives a description of a two-dimensional cellular automaton in terms of a finite state set and local transition rules defined on it.
Keywords: cellular automaton, firing squad synchronization problem, twodimensional rectangle synchronization.