Algorithms for Leader Election by Cellular Automata

We present two cellular algorithms, in O(n) and respectively in O(w²), for the leader election problem on finite connected rings F and respectively finite connected subsets of ^d, of eccentricity w, for any fixed d. The problem consists of finding an algorithm such that when setting the elements of F to a special state, and all the others to a state #, the cellular automaton iterates a finite number of steps and sets only one precise element of F to a special state called leader state, and all the others to a different state. We describe the algorithms in detail, give their proofs and complexities, and discuss the possible extensions.