A Biologically-Motivated Synchronization Problem in Cellular Automata


  • Hiroshi Umeo Univ. of Osaka Electro-Communication




We study a biologically-motivated synchronization problem that gives a finite-state protocol for synchronizing cellular automata. The synchronization in cellular automata has been known as firing squad synchronization problem since its development, in which it was originally proposed by J. Myhill in the book edited by Moore [1964] to synchronize all/some parts of self-reproducing cellular automata. The problem has been studied extensively for more than fifty years. It is defined as follows:
given a one-dimensional array of n identical cellular automata, including a generalВ at one end that is activated at time t = 0, we want to design the automata such that, at some future time, all the cells will simultaneouslyВ and, for the first time, enter a special firingВ state. The problem has been referred to as achieving a macro-synchronization in micro-synchronization system and realizing a global synchronization using only local information exchange.

In this paper, we present a survey on recent developments in designing optimum- and non-optimum-time synchronization algorithms and their implementations for one- and two-dimensional cellular arrays. Several simple, state-efficient mapping schemes are proposed for embedding one-dimensional firing squad synchronization algorithms onto two-dimensional arrays. The discussions are made from a viewpoint of biological systems, including fault-tolerance, self-replication, self-reproduction, self-repairing and growing nature-based systems.

[1] E. F. Moore: The firing squad synchronization problem. in Sequential Machines, Selected Papers,В E. F. Moore, ed., Addison-Wesley, Reading MA.,(1964), pp. 213-214.

[2] H. Umeo: Firing squad synchronization problem in cellular automata. In Encyclopedia of Complexity and System Science, R. A. Meyers (Ed.), Springer, Vol.4(2009), pp.3537-3574.






Conference Contributions