Algorithms for leader election by cellular automata

We present two cellular algorithms, in O(n) and respectively in O(w(2)), for the leader election problem on finite connected rings F and respectively finite connected subsets of Z(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. (C) 2001 Elsevier Science.