A Simple Optimum-Time FSSP Algorithm for Multi-Dimensional Cellular Automata

Hiroshi Umeo
(Univ. of Osaka Electro-Communication, Japan)
Kinuo Nishide
(Univ. of Osaka Electro-Communication, Japan)
Keisuke Kubo
(Univ. of Osaka Electro-Communication, Japan)

The firing squad synchronization problem (FSSP) 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 simple recursive-halving based optimum-time synchronization algorithm that can synchronize any rectangle arrays of size m*n with a general at one corner in m+n+max(m, n)-3 steps. The algorithm is a natural expansion of the well-known FSSP algorithm proposed by Balzer [1967], Gerken [1987], and Waksman [1966] and it can be easily expanded to three-dimensional arrays, even to multi-dimensional arrays with a general at any position of the array.

In Enrico Formenti: Proceedings 18th international workshop on Cellular Automata and Discrete Complex Systems and 3rd international symposium Journées Automates Cellulaires (AUTOMATA&JAC 2012), La Marana, Corsica, September 19-21, 2012, Electronic Proceedings in Theoretical Computer Science 90, pp. 151–165.
Published: 13th August 2012.

ArXived at: http://dx.doi.org/10.4204/EPTCS.90.13 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org