An Optimum-Time Square Synchronization Algorithm:
One-Sided Recursive-Halving Marking Based
Hiroshi Umeo, Hiroki Uchino and Akira Nomura
The firing squad synchronization problem (FSSP, for short) on cellular automata has been studied extensively for more than fifty years, and a rich variety of synchronization algorithms have been proposed for one and two-dimensional cellular automata. In the present paper, we propose a new optimum-time FSSP algorithm for two-dimensional square cellular automata. The algorithm can synchronize any square arrays of size n × n with a general at one corner in exactly 2n − 2 steps. It is based on a new technique called one-sided recursive-halving marking and is quite different from the well known classical FSSP algorithm proposed by Beyer [1969] and Shinahr [1974].
Keywords: Cellular automata, attractor, pseudo-exhaustive (PE) bit, point attractor, reachability tree