A new 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 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 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 124-state 45128-rule implementation of the algorithm is also given.