he 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 [1962]) 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 [1962] 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 [1966], Balzer [1967], Gerken [1987], and Mazoyer [1987].В We show that the algorithm has ...
