Skip to Main content Skip to Navigation

Leader Election by d Dimensional Cellular Automata

Abstract : We present a cellular algorithm in O(w^2) for the leader election problem on a finite connected subset F of Z^d of diameter w, for any fixed d. The problem consists in 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 eventually sets only one precise element of F to a special state called leader state. We describe the algorithm in detail, prove it and its complexity, and discuss the possible extensions on more general Cayley graphs.
Document type :
Complete list of metadata
Contributor : Colette Orange Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 9:09:52 AM
Last modification on : Saturday, September 11, 2021 - 3:19:18 AM


Files produced by the author(s)


  • HAL Id : hal-02101924, version 1



Codrin Nichitiu, Eric Remila. Leader Election by d Dimensional Cellular Automata. [Research Report] LIP RR-1999-01, Laboratoire de l'informatique du parallélisme. 1999, 2+10p. ⟨hal-02101924⟩



Les métriques sont temporairement indisponibles