A Survey on Optimum-Time Firing Squad Synchronization Algorithms for One-Dimensional Cellular Automata
Hiroshi Umeo, Masaya Hisaoka and Takashi Sogabe
The firing squad synchronization problem has been studied extensively for more than forty years, and a rich variety of synchronization algorithms have been proposed. In the present paper, we examine the state transition rule sets for the famous firing squad synchronization algorithms that give a finite-state protocol for synchronizing large-scale cellular automata and present a comparative study of the optimum-time synchronization protocols for one-dimensional cellular automata. The protocols being compared are Balzer [1], Gerken [4], Mazoyer [8], Waksman [23] and a number of revised versions thereof. We show that the first transition rule set designed by Waksman [23] includes fundamental errors which cause unsuccessful firings and that ninety-three percent of the rules are redundant. In addition, the transition rule sets reported by Balzer [1], Gerken [4] and Mazoyer [8] are found to include several redundant rules. We present herein a survey and a comparison of the quantitative and qualitative aspects of the optimum-time synchronization algorithms developed thus far for one-dimensional cellular arrays. Several new results and viewpoints are also given.