Synchronizing Multi-Dimensional Cellular Automata in Optimum-Time

摘要

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 algorithms 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. The algorithm proposed is isotropic concerning the side-lengths of multi-dimensional arrays and its algorithmic correctness is transparent and easily verified.