Paper Info
Title
Correction, Optimization and Verification of Transition Rule Set for Waksman's Firing Squad Synchronization Algorithm
Abstract
In 1966, A. Waksman proposed a Ib-state firing squad synchronization algorithm, which is known, together with an unpublished Goto's algorithm, as the first-in-the-world optimum-time firing algorithm. Waksman described his algorithm in terms of a finite state transition table, however, it has been reported in the talks of cellular automata researchers that some fatal errors were included in the Waksman's transition table. In this paper we correct all errors included in his original transition table and give a complete list of transition rules which yield successful firings for any array less than 10000 cells. In our correction, ninety-three percent reduction has been made in the number of Waksman's original transition rules. It has been shown that two-hundred and two rules are necessary and sufficientones for the Waksman's optimum-time firing squad synchronization.
Year
DOI
Venue
2000
10.1007/978-1-4471-0709-5_18
cellular automata for research and industry
Keywords
Field
DocType
firing squad synchronization algorithm,transition rule set
Cellular automaton,State transition table,Synchronization,Computer science,Algorithm,Theoretical computer science,Finite state,Selection rule,Synchronization algorithm,Goto
Conference
Citations 
PageRank 
References 
6
0.70
5
Authors
3
Name
Order
Citations
PageRank
Hiroshi Umeo136153.61
Takashi Sogabe2252.45
Nomura, Y.3319.51