Leader Election without Compass in Some Hyperbolic and Euclidean Cellular Automata - Archive ouverte HAL Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2001

Leader Election without Compass in Some Hyperbolic and Euclidean Cellular Automata

(1) , (1) , (1)
1

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

Partager

Gmail Facebook Twitter LinkedIn More