Leader Election without Compass in Some Hyperbolic and Euclidean Cellular Automata

Abstract : We present a linear time algorithm for the networking and distributed computing problem of leader election (LE). Given a graph, its vertices represent processors (here finite state machines), and its edges communication lines (here synchronous). The LE problem consists in finding a protocol for a family of graphs such that after iterating it, a vertex, edge or cycle be distinguished by a special state called leader. Here the graphs are only required to be connected, and without holes. We describe the algorithm in full detail on a special class of planar graphs, prove its correctness and show how it extends to other classes.
Document type :
Reports
Complete list of metadatas

https://hal-lara.archives-ouvertes.fr/hal-02101930
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:10:01 AM
Last modification on : Friday, May 17, 2019 - 1:39:22 AM

File

RR2001-08.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101930, version 1

Collections

Citation

Codrin Nichitiu, Christophe Papazian, Eric Remila. Leader Election without Compass in Some Hyperbolic and Euclidean Cellular Automata. [Research Report] LIP RR-2001-08, Laboratoire de l'informatique du parallélisme. 2001, 2+12p. ⟨hal-02101930⟩

Share

Metrics

Record views

6

Files downloads

8