Abstract : 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.
Résumé : 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.
