 |
HAL-LARA Libre accès aux rapports scientifiques et techniques |
 |
Reports
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.
https://hal-lara.archives-ouvertes.fr/hal-02101924
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:09:52 AM
Last modification on : Tuesday, May 4, 2021 - 9:10:01 PM
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:09:52 AM
Last modification on : Tuesday, May 4, 2021 - 9:10:01 PM
File
RR1999-01.pdf
Files produced by the author(s)
