\input zb-basic
\input zb-ioport
\iteman{io-port 05978151}
\itemau{Umeo, Hiroshi; Yanagihara, Takashi}
\itemti{Smallest implementations of optimum-time firing squad synchronization algorithms for one-bit-communication cellular automata.}
\itemso{Malyshkin, Victor (ed.), Parallel computing technologies. 11th international conference, PaCT 2011, Kazan, Russia, September 19-23, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-23177-3/pbk). Lecture Notes in Computer Science 6873, 210-223 (2011).}
\itemab
Summary: Synchronization of large-scale networks is an important and fundamental computing primitive in parallel and distributed systems. The firing squad synchronization problem (FSSP) on cellular automata (CA) has been studied extensively for more than fifty years, and a rich variety of synchronization algorithms has been proposed for not only one-dimensional but two-dimensional arrays. In the present paper, we study the FSSP on 1-bit-communication cellular automata, $\text{CA}_{\text{1-bit}}$. The $\text{CA}_{\text{1-bit}}$ is a weakest subclass of CAs in which the amount of inter-cell communication bits transferred among neighboring cells at one step is restricted to 1-bit. We propose two state-efficient implementations of optimum-time FSSP algorithms for the $\text{CA}_{\text{1-bit}}$ and show that the communication restriction has no influence on the design of optimum-time FSSP algorithms. The implementations proposed are the smallest ones, known at present.
\itemrv{~}
\itemcc{}
\itemut{}
\itemli{doi:10.1007/978-3-642-23178-0\_19}
\end