A Biologically-Motivated Synchronization Problem in Cellular Automata

Authors

  • Hiroshi Umeo Univ. of Osaka Electro-Communication

DOI:

https://doi.org/10.11145/cb.v3i1.691

Abstract

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.

Downloads

Published

2016-04-09

Issue

Vol. 3 No. 1 (2016)

Section

Conference Contributions

License

The journal Biomath Communications is an open access journal. All published articles are immeditely available online and the respective DOI link activated. All articles can be access for free and no reader registration of any sort is required. No fees are charged to authors for article submission or processing. Online publications are funded through volunteer work, donations and grants.

Authors who publish with this journal agree to the following terms:

  • Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License 4.0 that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
  • Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
  • Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).