Leader Election without Compass in Some Hyperbolic and Euclidean Cellular Automata - LARA - Libre accès aux rapports scientifiques et techniques
Rapport (Rapport De Recherche) Année : 2001

Leader Election without Compass in Some Hyperbolic and Euclidean Cellular Automata

Résumé

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.
Nous présentons un algorithme en temps linéaire, pour résoudre le problème de l’élection d'un chef sur un graphe dont chaque sommet est un automate fini '(un ordinateur) et chaque arête, un lien de communication (modèle synchrone). Le problème de l’élection consiste à trouver un algorithme pour une famille de graphe qui, après un nombre fini de calcul distingue un sommet, une arête ou un cycle particulier dans un état de "chef". Ici, les graphes considérés doivent être connexes et sans trous. Nous décrivons l’algorithme en détail sur une classe de graphes particulière,prouvons son exactitude et montrons comment il s'étend aux autres classes.
Fichier principal
Vignette du fichier
RR2001-08.pdf (294.2 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-02101930 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02101930 , version 1

Citer

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⟩
27 Consultations
49 Téléchargements

Partager

More