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 :
Reports
Complete list of metadatas

https://hal-lara.archives-ouvertes.fr/hal-02101924
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:09:52 AM
Last modification on : Wednesday, November 20, 2019 - 2:51:18 AM

File

RR1999-01.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101924, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

18

Files downloads

51