Leader Election by d Dimensional Cellular Automata - LARA - Libre accès aux rapports scientifiques et techniques
Rapport (Rapport De Recherche) Année : 1999

Leader Election by d Dimensional Cellular Automata

Résumé

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.
Nous présentons un algorithme cellulaire en O(w^2) pour le problème d'élection d'un général sur un sous-ensemble fini connexe F\subset\Z^d de diamètre w, pour n'importe quel d fixé. Le problème consiste à trouver un algorithme tel que lorsqu'on met les éléments de F dans un état spécial et tous les autres dans un état #, l'automate cellulaire itère un nombre fini de pas, et met un seul élément de F dans un état spécial nommé état général. Nous décrivons l'algorithme en détail, démontrons sa correction et sa complexité et discutons des extensions possibles à des graphes de Cayley plus généraux.
Fichier principal
Vignette du fichier
RR1999-01.pdf (259.32 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

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

Identifiants

  • HAL Id : hal-02101924 , version 1

Citer

Codrin Nichitiu, Eric Remila. Leader Election by d Dimensional Cellular Automata. [Research Report] LIP RR-1999-01, Laboratoire de l'informatique du parallélisme. 1999, 2+10p. ⟨hal-02101924⟩
23 Consultations
140 Téléchargements

Partager

More