Configuration Symmetry and Performance Upper Bound of One-Dimensional Cellular Automata for the Leader Election Problem
Peter Banda, John Caughman and Jiri Pospichal
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.
Keywords: One-dimensional cellular automata, leader election problem, upper bound performance, symmetric configuration, loosely-coupled configuration