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.
Origine : Fichiers produits par l'(les) auteur(s)