Firing Squad Synchronization Algorithms for Two-Dimensional Cellular Automata

摘要

The firing squad synchronization problem on cellular automata has been studied extensively for more than forty 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 firing squad synchronization algorithms for large-scale two-dimensional cellular automata. Several state-efficient implementations and new viewpoints for the two-dimensional synchronization algorithms are given.