Realizing Global Synchronizations for Locally-Connected Two-Dimensional Rectangle Cellular Arrays

Synchronization of large-scale networks is an important and fundamental computing primitive in parallel and distributed systems. The synchronization in cellular automata has been known as firing squad synchronization problem (FSSP) since its development. The FSSP has been studied extensively for more than fifty years, and a rich variety of synchronization algorithms have been proposed so far. In the present paper, we give a survey on recent developments in FSSP algorithms for two-dimensional rectangle cellular automata. Several state-efficient new implementations of synchronization algorithms are also given.