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