A new reconstruction and the first implementation of Goto’s FSSP algorithm

Hiroshi Umeo, Mitsuki Hirota, Youhei Nozaki, Keisuke Imai and Takashi Sogabe

Applied Mathematics and Computation, 2018, vol. 318, issue C, 92-108

Abstract: The 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 state-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 Θ(nlog n) minimum-state-change complexity for synchronizing n cells. The algorithm is optimum not only in time but also in state-change complexities. We show that the reconstructed algorithm can be generalized as to the initial general’s position and its implementation on a cellular automaton with 434 internal states and 13,328 state-transition rules is also given. The general purpose of this investigation is to achieve more insights into the structure of the classical minimum-time FSSP solutions and such insights would be helpful in the design of new FSSP algorithms.

Keywords: Cellular automaton; Firing squad synchronization problem; FSSP (search for similar items in EconPapers)
Date: 2018
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S009630031730303X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:318:y:2018:i:c:p:92-108

DOI: 10.1016/j.amc.2017.05.015

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().