Reference : Configuration Symmetry and Performance Upper Bound of One-Dimensional Cellular Automa...
Scientific journals : Article
Physical, chemical, mathematical & earth Sciences : Mathematics
Engineering, computing & technology : Computer science
Computational Sciences
Configuration Symmetry and Performance Upper Bound of One-Dimensional Cellular Automata for the Leader Election Problem
Banda, Peter mailto [Comenius University > Department of Applied Informatics]
Caugmann, John IV. [> >]
Pospichal, Jiri [> >]
Journal of Cellular Automata
[en] one-dimensional cellular automata ; leader election problem ; upper bound performance ; symmetric configuration ; loosely-coupled configuration
[en] Leader election plays a crucial role in numerous distributed protocols and biological societies. Yet, there is a fundamental gap in understanding its simplest variant employing components that are fully uniform, deterministic, and anonymous, such as in one-dimensional cellular automata (CA). In our previous work we found several binary CAs that elect a leader by using spatial-temporal patterns, domains and particles, which carry and exchange information across distance. The best strategy reached performance of 94 -99% with a modulo 6 limitation for the number of cells. As opposed to state-of-the-art distributed algorithms, a CA consists just of binary components without any extra memory or communication capabilities, and therefore operates with minimal resources possible.

In this paper we identify fundamental limitations of leader election for one-dimensional CAs and formulate an upper bound on performance. We show that configurations that are symmetric or loosely-coupled are insolvable. The proportion of configurations that are insolvable decreases dramatically with the system size. Our findings could help to design more effective distributed protocols and also to model biological processes such as morphogenesis of cell differentiation, where leader election breaks symmetry in a newly formed organism.

There is no file associated with this reference.

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.