An Optimum-Time Firing Squad Synchronization Algorithm for Two-Dimensional Rectangle Arrays - Freezing-Thawing Technique Based
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 to m x 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.
firing squad synchronization problem cellular automaton two-dimensional rectangle synchronization