A reconstruction of the first FSSP algorithm
Abstracthe firing squad synchronization problem (FSSP) on cellular automata has been studied extensively for more than fifty years, and a rich variety of synchronization algorithms has been proposed. Goto's FSSP algorithm (Goto ) has been known as the first minimum-time FSSP algorithm, however the paper itself had been a completely unknown one in the research community of cellular automata for a long time due to its hard accessibility. In the present paper, we reconstruct the Goto's FSSP algorithm and present the first small-state implementation.В The implementation is realized on a cellular automaton having 165-state and 4378 transition rules and the realization is far smaller than Goto  imagined, where he thought that it would require many thousands of thousands states. It is shown that the reconstructed algorithm uses a quite different synchronization mechanism in comparison with the designs employed in Waksman , Balzer , Gerken , and Mazoyer .В We show that the algorithm has ...