Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Reports

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 metadata

https://hal-lara.archives-ouvertes.fr/hal-02101930
Contributor : Colette ORANGE Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 9:10:01 AM
Last modification on : Saturday, September 11, 2021 - 3:19:17 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

4

Files downloads

3