A class of time-optimum FSSP algorithms for multi-dimensional cellular arrays

• The paper proposes a new class of time-optimum FSSP algorithms for multi-dimensional cellular arrays.
• The 2D FSSP algorithm proposed can be easily expanded to 3D arrays, even to multi-dimensional arrays.
• The class includes several well-known 1D FSSP algorithms proposed by Balzer [1], Gerken [3], and Waksman [19].
• The isotropic property of the algorithm yields an easy verification for the multi-dimensional FSSP algorithms.
• Several lower bounds on time complexity in multi-dimensional FSSP algorithms are established.

The firing squad synchronization problem (FSSP) on cellular automata has been studied extensively for more than fifty years, and a rich variety of synchronization algorithms has been proposed not only for one-dimensional arrays but also for two-dimensional arrays. In the present paper, we propose a new class of time-optimum FSSP algorithms for multi-dimensional cellular arrays. The algorithm is based on a simple recursive-halving marking schema and it can synchronize any two-dimensional (2D) rectangular arrays of size m×nm×n with a general at one corner in m+n+max(m,n)-3m+n+max(m,n)-3 optimum-steps. The algorithm is a natural expansion of the well-known one-dimensional (1D) FSSP algorithms proposed by Balzer (1967), Gerken (1987), and Waksman (1966) and it can be easily expanded to three-dimensional (3D) arrays, even to multi-dimensional arrays. The algorithm proposed is isotropic concerning the side-lengths of multi-dimensional arrays and this isotropic property yields algorithmic correctness and easy verification for the multi-dimensional time-optimum FSSP algorithms designed.