Anonymous Leader Election in One- and Two-Dimensional Cellular Automata

Leader election plays a crucial role in numerous distributed protocols, multi-agent systems and biological societies. Yet there is a fundamental gap in understanding its simplest variant, such as, in cellular automata, employing components that are fully uniform, deterministic, and anonymous.

In this thesis, we investigate various one- and two-dimensional binary state cellular automata that elect a leader by transforming a random initial configuration to a state where exactly one arbitrary cell is active (leader). A cellular automaton (CA) is a distributed system with a spatial topology where each processor (cell) is locally connected to its neighbors. A transition rule is represented by a look-up table, which is uniform, i.e., shared among all cells. We show that leader election is possible even in the minimal, anonymous, and uniform architecture of a binary CA. Despite being one of the structurally simplest distributed systems, a CA can exhibit various types of behavior, including complex dynamics and self-organization.

Our methodology leverages evolution of CAs by employing genetic algorithms, where chromosomes encoding candidate look-up tables undergo selection, cross-over and mutation.
Even though CA's transition rules are just local and uniform, the leader election task is global and requires coordination of all cells. The findings show that the emergent dynamics of the best binary CAs are characterized by sophisticated coordination and global computation of cells, a product of spatio-temporal structures or events, namely regular domains, particles and particle interactions, known from the theory of computational mechanics. This collision-based computing enables CA to carry and exchange information over distances, eventually eliminating all but one candidate for leader. In two dimensions, slowly-contracting regions connected by lines of active cells propagate throughout the lattice and sweep any remaining active cells, before shrinking to a single cell (leader). The best strategies for both instances show a remarkably high performance rate of 0.99. In one-dimensional case the number of cells N is often modulo-restricted, such as in the best-performing CA called the strategy of mirror particles, where N is restricted to 5 mod 6. We also analyze the dynamics of two-dimensional CAs by stability measures: the Derrida measure, and the damage spreading with a discrete version of Lyapunov stability. In general, the more complex the dynamics, the better-performing the CA.

Furthermore, we identify fundamental limitations of leader election for one- and two-dimensional CAs. More precisely, we show that configurations that are symmetric or loosely-coupled are principally unsolvable.
The proportion of these configurations, however, decreases dramatically with the system size. We enumerate such unsolvable configurations using linear algebra and group theory and formulate a universal upper bound on performance for the anonymous leader election problem in CA.

Our results pave the way to new distributed algorithms that are more robust and efficient than state-of-the-art systems. Our cellular automata consist of only binary components, without any extra memory or communication capabilities, and therefore use minimal resources possible. Our findings are also relevant for better understanding leader election in nature, in order to model biological processes such as morphogenesis of cell differentiation.