A Simple Optimum-Time Firing Squad Synchronization Algorithm for Two-Dimensional Rectangle Arrays

The firing squad synchronization problem on cellular automata has been studied extensively for more than forty years, and a rich variety of synchronization algorithms have been proposed for not only one-dimensional arrays but two-dimensional arrays. In the present paper, we propose a new and simpler 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. An implementation for the algorithm in terms of local transition rules is also given.