References of "Journal of Cellular Automata"
     in
Bookmark and Share    
Peer Reviewed
See detailConfiguration Symmetry and Performance Upper Bound of One-Dimensional Cellular Automata for the Leader Election Problem
Banda, Peter UL; Caugmann, John IV.; Pospichal, Jiri

in Journal of Cellular Automata (2015), 10(1-2), 1-21

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 ... [more ▼]

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. [less ▲]

Detailed reference viewed: 49 (4 UL)
Full Text
Peer Reviewed
See detailRule Vector Graph (RVG) To Design Linear Time Algorithm for Identifying the Invertibility of Periodic-Boundary Three Neighborhood Cellular Automata.
Maitii, Nirmalya S.; Ghosh, Soumyabrata UL; Sikdar, Biplab K. et al

in Journal of Cellular Automata (2012), 7(4),

Detailed reference viewed: 29 (2 UL)