An FSSP on Torus

The firing squad synchronization problem (FSSP) has been studied extensively for more than fifty years, and a rich variety of synchronization algorithms has been proposed. In the present paper, we give a lower bound of FSSP algorithms for two-dimensional (2D) torus and present a minimum-time FSSP algorithm that can synchronize any 2D torus of size m × n in max (m, n) + floor min(m, n)/2 floor steps. It is shown that the lower bound and the algorithm given for the 2D torus is a generalization of the known results on one-dimensional (1D) rings (A. Berthiaume et al. [2004]) and it can be generalized to multi-dimensional rings.