Élection du chef - Leader election

Dans l' informatique distribuée , l' élection du leader est le processus consistant à désigner un seul processus comme organisateur d'une tâche répartie entre plusieurs ordinateurs (nœuds). Avant que la tâche ne commence, tous les nœuds du réseau ne savent pas quel nœud servira de "chef" (ou coordinateur ) de la tâche, ou incapables de communiquer avec le coordinateur actuel. Cependant, après l'exécution d'un algorithme d'élection de leader, chaque nœud du réseau reconnaît un nœud particulier et unique en tant que leader de la tâche.

Les nœuds du réseau communiquent entre eux pour décider lequel d'entre eux passera à l'état « leader ». Pour cela, ils ont besoin d'une certaine méthode afin de briser la symétrie entre eux. Par exemple, si chaque nœud a des identités uniques et comparables, les nœuds peuvent comparer leurs identités et décider que le nœud avec l'identité la plus élevée est le leader.

La définition de ce problème est souvent attribuée à LeLann, qui l'a formalisé comme une méthode pour créer un nouveau jeton dans un réseau token ring dans lequel le jeton a été perdu.

Les algorithmes d'élection de leader sont conçus pour être économiques en termes de nombre total d' octets transmis et de temps. L'algorithme suggéré par Gallager, Humblet et Spira pour les graphes généraux non orientés a eu un fort impact sur la conception d'algorithmes distribués en général et a remporté le prix Dijkstra pour un article influent sur l'informatique distribuée.

De nombreux autres algorithmes ont été suggérés pour différents types de graphes de réseau , tels que les anneaux non orientés , les anneaux unidirectionnels, les graphes complets, les grilles, les graphes d'Euler orientés et autres. Une méthode générale qui découple la question de la famille de graphes de la conception de l'algorithme d'élection de leader a été suggérée par Korach , Kutten et Moran .

Définition

Le problème de l'élection du leader est que chaque processeur décide finalement s'il est un leader ou non, sous réserve qu'exactement un processeur décide qu'il est le leader. Un algorithme résout le problème de l'élection du leader si :

Les états des processeurs sont divisés en états élus et non élus. Une fois élu, il reste élu (de même s'il n'est pas élu).
Dans chaque exécution, exactement un processeur est élu et les autres déterminent qu'ils ne sont pas élus.

Un algorithme d'élection de leader valide doit remplir les conditions suivantes :

Terminaison : l'algorithme doit se terminer dans un temps fini une fois le leader sélectionné. Dans les approches randomisées, cette condition est parfois affaiblie (par exemple, nécessitant une terminaison avec probabilité 1).
Unicité : il y a exactement un processeur qui se considère comme leader.
Accord : tous les autres transformateurs savent qui est le leader.

Un algorithme pour l'élection du chef peut varier dans les aspects suivants :

Mécanisme de communication : les processeurs sont soit synchrones dans lesquels les processus sont synchronisés par un signal d'horloge, soit asynchrones où les processus s'exécutent à des vitesses arbitraires.
Noms de processus : si les processus ont une identité unique ou sont indiscernables (anonymes).
Topologie du réseau : par exemple, anneau , graphe acyclique ou graphe complet .
Taille du réseau : l'algorithme peut ou non utiliser la connaissance du nombre de processus dans le système.

Algorithmes

Élection du leader dans les anneaux

Topologie de réseau en anneau

Un réseau en anneau est une topologie à graphe connecté dans laquelle chaque nœud est exactement connecté à deux autres nœuds, c'est-à-dire que pour un graphe à n nœuds, il y a exactement n arêtes reliant les nœuds. Un anneau peut être unidirectionnel, ce qui signifie que les processeurs ne communiquent que dans un sens (un nœud ne peut envoyer des messages qu'à gauche ou uniquement à droite), ou bidirectionnel, ce qui signifie que les processeurs peuvent transmettre et recevoir des messages dans les deux sens (un nœud peut envoyer des messages à gauche et à droite).

Anneaux anonymes

Un anneau est dit anonyme si tous les processeurs sont identiques. Plus formellement, le système a la même machine à états pour chaque processeur. Il n'y a pas d'algorithme déterministe pour élire un leader dans les anneaux anonymes, même lorsque la taille du réseau est connue des processus. Cela est dû au fait qu'il n'y a aucune possibilité de briser la symétrie dans un anneau anonyme si tous les processus s'exécutent à la même vitesse. L'état des processeurs après quelques étapes ne dépend que de l'état initial des nœuds voisins. Ainsi, parce que leurs états sont identiques et exécutent les mêmes procédures, à chaque tour les mêmes messages sont envoyés par chaque processeur. Par conséquent, chaque état de processeur change également de manière identique et, par conséquent, si un processeur est élu en tant que leader, tous les autres le sont également.

Pour plus de simplicité, prouvez-le dans des anneaux synchrones anonymes. Démontrer par contradiction. Considérons un anneau anonyme R de taille n>1. Supposons qu'il existe un algorithme "A" pour résoudre l'élection du leader dans cet anneau anonyme R.

Lemme : après le tour de l'exécution admissible de A dans R, tous les processus ont les mêmes états. ${\style d'affichage k}$

Preuve. prouver par récurrence sur . ${\style d'affichage k}$

Cas de base : : tous les processus sont à l'état initial, donc tous les processus sont identiques. ${\style d'affichage k=0}$

Hypothèse d'induction : supposons que le lemme est vrai pour les tours. ${\style d'affichage k-1}$

Étape inductive : dans round , chaque processus envoie le même message à droite et envoie le même message à gauche. Étant donné que tous les processus sont dans le même état après le tour , au tour k, chaque processus recevra le message du bord gauche et recevra le message du bord droit. Étant donné que tous les processus reçoivent les mêmes messages au cours du tour , ils sont dans le même état après le tour . ${\style d'affichage k}$ ${\style d'affichage m_{r}}$ ${\style d'affichage m_{l}}$ ${\style d'affichage k-1}$ ${\style d'affichage m_{r}}$ ${\style d'affichage m_{l}}$ ${\style d'affichage k}$ ${\style d'affichage k}$

Le lemme ci-dessus contredit le fait qu'après un nombre fini de tours dans une exécution de A, un processus est entré dans l'état élu et d'autres processus sont entrés dans l'état non élu.

Élection aléatoire (probabiliste) du chef

Une approche courante pour résoudre le problème de l'élection du leader dans les anneaux anonymes est l'utilisation d' algorithmes probabilistes . Dans de telles approches, les processeurs assument généralement certaines identités basées sur une fonction probabiliste et les communiquent au reste du réseau. A la fin, grâce à l'application d'un algorithme, un leader est sélectionné (avec une forte probabilité).

Anneau asynchrone

Algorithme O(nlogn) pour anneau asynchrone

Puisqu'il n'y a pas d'algorithme pour les anneaux anonymes (prouvé ci-dessus), les anneaux asynchrones seraient considérés comme des anneaux asynchrones non anonymes. Dans les anneaux non anonymes, chaque processus a un unique , et ils ne connaissent pas la taille de l'anneau. L'élection du leader dans les anneaux asynchrones peut être résolue par un algorithme utilisant des messages ou des messages. ${\identifiant du style d'affichage}$ ${\style d'affichage O(n^{2})}$ $O(n\log n)$

Dans l' algorithme, chaque processus envoie un message avec son bord gauche. Attend ensuite un message du bord droit. Si le dans le message est supérieur au sien , transfère le message vers le bord gauche ; sinon ignore le message et ne fait rien. Si le dans le message est égal au sien , alors envoie un message vers la gauche m'annonçant que je suis élu. D'autres processus transfèrent l'annonce vers la gauche et se transforment en non-élus. Il est clair que la borne supérieure est pour cet algorithme. ${\style d'affichage O(n^{2})}$ ${\identifiant du style d'affichage}$ ${\identifiant du style d'affichage}$ ${\identifiant du style d'affichage}$ ${\identifiant du style d'affichage}$ ${\identifiant du style d'affichage}$ ${\style d'affichage O(n^{2})}$

Dans l' algorithme, il fonctionne par phases. Lors de la e phase, un processus déterminera s'il est le gagnant parmi les voisins de gauche et de droite . Si c'est un gagnant, alors le processus peut passer à la phase suivante. Dans la phase , chaque processus doit déterminer lui-même est un gagnant ou non en envoyant un message avec ses voisins de gauche et de droite (le voisin ne transmet pas le message). Le voisin répond un uniquement si le dans le message est plus grand que celui du voisin , sinon répond un . Si reçoit deux s, un de gauche, un de droite, alors est le vainqueur de la phase . Dans la phase , les gagnants en phase nécessaire d'envoyer un message avec son à la gauche et les voisins de droite. Si les voisins du chemin reçoivent dans le message un plus grand que leur , alors transférez le message au prochain voisin, sinon répondez un . Si le e voisin reçoit le plus grand que le sien , alors renvoie un , sinon répond un . Si le processus reçoit deux s, alors c'est le gagnant de la phase . Dans la dernière phase, le gagnant final recevra le sien dans le message, puis terminera et enverra un message de fin aux autres processus. Dans le pire des cas, à chaque phase il y a au plus des gagnants, où est le numéro de la phase. Il y a des phases au total. Chaque gagnant envoie dans l'ordre des messages dans chaque phase. Ainsi, la complexité des messages est . $O(n\log n)$ ${\style d'affichage k}$ $2^{k}$ $2^{k}$ ${\style d'affichage P}$ ${\identifiant du style d'affichage}$ $ACK$ ${\identifiant du style d'affichage}$ ${\identifiant du style d'affichage}$ $ACK_{défaut}$ ${\style d'affichage P}$ $ACK$ ${\style d'affichage P}$ ${\style d'affichage k}$ ${\style d'affichage k-1}$ ${\identifiant du style d'affichage}$ $2^{k}$ $2^{k}$ ${\identifiant du style d'affichage}$ ${\identifiant du style d'affichage}$ $ACK_{défaut}$ $2^{k}$ ${\identifiant du style d'affichage}$ ${\identifiant du style d'affichage}$ $ACK$ $ACK_{défaut}$ $ACK$ ${\style d'affichage k}$ ${\identifiant du style d'affichage}$ ${\frac {n}{2^{k}+1}}$ ${\style d'affichage k}$ $\lceil \log(n-1)\rceil$ $2^{k}$ $O(n\log n)$

Anneau synchrone

Dans le livre Distributed Computing d'Attiya et Welch, ils ont décrit un algorithme non uniforme utilisant des messages en anneau synchrone avec une taille d'anneau connue . L'algorithme fonctionne par phases, chaque phase a des tours, chaque tour est une unité de temps. Dans la phase , s'il y a un processus avec , alors le processus envoie un message de fin aux autres processus (l'envoi de messages de fin coûte des tours). Sinon, passez à la phase suivante. L'algorithme vérifiera s'il existe un numéro de phase égal à un processus , puis effectuera les mêmes étapes que phase. A la fin de l'exécution, le minimum sera élu chef. Il a utilisé exactement les messages et les tours. ${\style d'affichage O(n)}$ ${\style d'affichage n}$ ${\style d'affichage n}$ $id=0$ ${\style d'affichage n}$ ${\identifiant du style d'affichage}$ ${\identifiant du style d'affichage}$ ${\style d'affichage n}$ $n(minimum\_id+1)$

Itai et Rodeh ont introduit un algorithme pour un anneau unidirectionnel avec des processus synchronisés. Ils supposent que la taille de l'anneau (nombre de nœuds) est connue des processus. Pour un anneau de taille n, un à n processeurs sont actifs. Chaque processeur décide avec une probabilité de a^(-1) s'il devient candidat. A la fin de chaque phase, chaque processeur calcule le nombre de candidats c et s'il est égal à 1, il devient leader. Pour déterminer la valeur de c, chaque candidat envoie un jeton (caillou) au début de la phase qui fait le tour de l'anneau, revenant après exactement n unités de temps à son émetteur. Chaque processeur détermine c en comptant le nombre de cailloux qui sont passés à travers. Cet algorithme réalise l'élection du leader avec une complexité de message attendue de O(nlogn). Une approche similaire est également utilisée dans laquelle un mécanisme de temporisation est utilisé pour détecter les blocages dans le système. Il existe également des algorithmes pour les anneaux de tailles spéciales telles que la taille principale et la taille impaire.

Algorithme uniforme

Dans les approches typiques de l'élection des dirigeants, la taille de l'anneau est supposée connue des processus. Dans le cas des anneaux anonymes, sans recours à une entité externe, il n'est pas possible d'élire un leader. Même en supposant qu'un algorithme existe, le leader n'a pas pu estimer la taille de l'anneau. c'est-à-dire que dans n'importe quel anneau anonyme, il y a une probabilité positive qu'un algorithme calcule une mauvaise taille d'anneau. Pour surmonter ce problème, Fisher et Jiang ont utilisé un soi-disant oracle de leader Ω? que chaque processeur peut demander s'il existe un leader unique. Ils montrent qu'à partir d'un certain point, il est garanti de renvoyer la même réponse à tous les processus.

Anneaux avec des identifiants uniques

Dans l'un des premiers travaux, Chang et Roberts ont proposé un algorithme uniforme dans lequel un processeur avec l'ID le plus élevé est sélectionné comme leader. Chaque processeur envoie son ID dans le sens des aiguilles d'une montre. Un processus qui reçoit un message et le compare au sien. S'il est plus gros, il le traverse, sinon il rejettera le message. Ils montrent que cet algorithme utilise au maximum les messages et dans le cas moyen. Hirschberg et Sinclair ont amélioré cet algorithme avec la complexité du message en introduisant un schéma de passage de message bidirectionnel permettant aux processeurs d'envoyer des messages dans les deux sens. ${\style d'affichage O(n^{2})}$ $O(n\log n)$
$O(n\log n)$

Élection du leader dans un maillage

Topologie de réseau maillé. Les nœuds rouges indiquent les coins, la bordure bleue et l'intérieur gris.

Le maillage est une autre forme populaire de topologie de réseau, en particulier dans les systèmes parallèles, les systèmes de mémoire redondante et les réseaux d'interconnexion.
Dans une structure maillée, les nœuds sont soit en coin (seulement deux voisins), en bordure (seulement trois voisins) ou à l'intérieur (avec quatre voisins). Le nombre d'arêtes dans une maille de taille axb est m=2ab-ab.

Maillage non orienté

Un algorithme typique pour résoudre l'élection du leader dans un maillage non orienté consiste à élire uniquement l'un des quatre nœuds d'angle comme leader. Étant donné que les nœuds de coin peuvent ne pas être au courant de l'état d'autres processus, l'algorithme doit d'abord réveiller les nœuds de coin. Un chef peut être élu comme suit.

Processus de réveil : dans lequel les nœuds initient le processus d'élection. Chaque initiateur envoie un message de réveil à tous ses nœuds voisins. Si un nœud n'est pas l'initiateur, il transmet simplement les messages aux autres nœuds. A ce stade, la plupart des messages sont envoyés. ${\style d'affichage k}$ ${\style d'affichage 3n+k}$
Processus électoral : l'élection en couronne se déroule au maximum en deux étapes avec des messages. ${\style d'affichage 6(a+b)-16}$
Terminaison : le leader envoie un message de terminaison à tous les nœuds. Cela nécessite au plus 2n messages.

La complexité du message est au plus de , et si le maillage est de forme carrée, . ${\style d'affichage 6(a+b)-16}$ ${\style d'affichage O({\sqrt {n}})}$

Maillage orienté

Un maillage orienté est un cas particulier où les numéros de port sont des étiquettes de boussole, c'est-à-dire nord, sud, est et ouest. L'élection du leader dans un maillage orienté est triviale. Nous avons seulement besoin de nommer un coin, par exemple « nord » et « est » et de s'assurer que le nœud sait qu'il est un leader.

Torus

Structure du réseau tore.

Un cas particulier d'architecture de maillage est un tore qui est un maillage avec « wrap-around ». Dans cette structure, chaque nœud a exactement 4 arêtes de connexion. Une approche pour élire un chef dans une telle structure est connue sous le nom d'étapes électorales. Semblable aux procédures dans les structures en anneau, cette méthode à chaque étape élimine les candidats potentiels jusqu'à ce qu'il ne reste finalement qu'un nœud candidat. Ce nœud devient le leader et notifie ensuite tous les autres processus de terminaison. Cette approche peut être utilisée pour atteindre une complexité de O(n). Des approches plus pratiques ont également été introduites pour traiter la présence de liens défectueux dans le réseau.

Élection en hypercubes

Topologie de réseau hypercube H_4.

Un Hypercube est un réseau composé de nœuds, chacun avec un degré et des bords. Des étapes électorales similaires à celles d'avant peuvent être utilisées pour résoudre le problème de l'élection du chef. À chaque étape, deux nœuds (appelés duellistes) s'affrontent et le gagnant est promu à l'étape suivante. Cela signifie qu'à chaque étape, seule la moitié des duellistes entrent dans l'étape suivante. Cette procédure se poursuit jusqu'à ce qu'il ne reste qu'un seul duelliste et qu'il devienne le leader. Une fois sélectionné, il notifie tous les autres processus. Cet algorithme nécessite des messages. Dans le cas des hypercubes non orientés, une approche similaire peut être utilisée mais avec une complexité de message plus élevée de . $H_{k}$ ${\style d'affichage n=2^{k}}$ ${\style d'affichage k}$ $O(n\log n)$ ${\style d'affichage O(n)}$ $O(n\log \log n)$

Élection en réseaux complets

Structure de réseau complète.

Les réseaux complets sont des structures dans lesquelles tous les processus sont connectés les uns aux autres, c'est-à-dire que le degré de chaque nœud est n-1, n étant la taille du réseau. Une solution optimale avec un message O(n) et une complexité spatiale est connue. Dans cet algorithme, les processus ont les états suivants :

Dummy : nœuds qui ne participent pas à l'algorithme d'élection du leader.
Passif : l'état initial des processus avant le démarrage.
Candidat : l'état des nœuds après le réveil. Les nœuds candidats seront considérés comme le leader.

Il existe une hypothèse selon laquelle bien qu'un nœud ne connaisse pas l'ensemble total des nœuds du système, il est nécessaire que, dans cet arrangement, chaque nœud connaisse l'identifiant de son successeur unique, qui est appelé voisin, et chaque nœud est connu par un autre. .

Tous les processeurs démarrent initialement dans un état passif jusqu'à ce qu'ils soient réveillés. Une fois que les nœuds sont éveillés, ils sont candidats pour devenir le leader. Sur la base d'un schéma de priorité, les nœuds candidats collaborent dans l'anneau virtuel. À un moment donné, les candidats prennent conscience de l'identité des candidats qui les précèdent sur le ring. Les candidats les plus prioritaires interrogent les moins bons sur leurs prédécesseurs. Les candidats moins prioritaires deviennent des mannequins après avoir répondu aux candidats plus prioritaires. Sur la base de ce schéma, le candidat ayant la priorité la plus élevée finit par savoir que tous les nœuds du système sont des mannequins, à l'exception de lui-même, auquel cas il sait qu'il est le leader.

L'algorithme ci-dessus n'est pas vrai et il a été corrigé avec un autre algorithme.

Techniques universelles d'élection de chef

Comme leur nom l'indique, ces algorithmes sont conçus pour être utilisés dans toutes les formes de réseaux de processus sans aucune connaissance préalable de la topologie d'un réseau ou de ses propriétés, telles que sa taille.

Crier

Shout (protocole) construit un arbre couvrant sur un graphe générique et élit sa racine comme leader. L'algorithme a un coût total linéaire dans la cardinalité des arêtes.

Méga-fusion

Cette technique est essentiellement similaire à la recherche d'un arbre couvrant minimum (MST) dans lequel la racine de l'arbre devient le leader. L'idée de base de cette méthode est que les nœuds individuels fusionnent les uns avec les autres pour former des structures plus grandes. Le résultat de cet algorithme est un arbre (un graphe sans cycle) dont la racine est le leader de tout le système. Le coût de la méthode de méga-fusion est où m est le nombre d'arêtes et n est le nombre de nœuds. ${\style d'affichage O(m+n\log n)}$

Yo-yo

Un exemple de procédure YO-YO. a) le réseau, b) le réseau orienté après la phase d' établissement , c) la phase YO- dans laquelle les valeurs source sont transmises, d) la phase-YO envoyant les réponses des puits, e) la structure mise à jour après la phase -YO.

Yo-yo (algorithme) est un algorithme de recherche minimum composé de deux parties : une phase de prétraitement et une série d'itérations. Dans la première phase ou configuration , chaque nœud échange son identifiant avec tous ses voisins et en fonction de la valeur, il oriente ses arêtes incidentes. Par exemple, si le nœud x a un identifiant plus petit que y, x s'oriente vers y. Si un nœud a un identifiant plus petit que tous ses voisins, il devient une source . En revanche, un nœud avec tous les bords vers l'intérieur (c'est-à-dire avec un identifiant plus grand que tous ses voisins) est un puits . Tous les autres nœuds sont des nœuds internes .
Une fois que toutes les arêtes sont orientées, la phase d' itération démarre. Chaque itération est une étape électorale au cours de laquelle certains candidats seront écartés. Chaque itération comporte deux phases: YO et -YO . Dans cette phase, les sources démarrent le processus pour propager à chaque puits les plus petites valeurs des sources connectées à ce puits.

Yo-

Une source (minimums locaux) transmet sa valeur à tous ses voisins externes
Un nœud interne attend de recevoir une valeur de tous ses voisins internes. Il calcule le minimum et l'envoie à l'extérieur.
Un puits (un nœud sans bord sortant) reçoit toutes les valeurs et calcule leur minimum.

-yo

Un évier envoie OUI aux voisins à partir desquels a vu la plus petite valeur et NON aux autres
Un nœud interne envoie OUI à tous les voisins internes dont il a reçu la plus petite valeur et NON aux autres. S'il ne reçoit qu'un seul NON, il envoie NON à tous.
Une source attend d'avoir reçu tous les votes. Si tout OUI, il survit et sinon, il n'est plus candidat.
Lorsqu'un nœud x envoie NON à un y voisin, la direction logique de ce bord est inversée.
Lorsqu'un nœud y reçoit NO d'un voisin extérieur, il inverse la direction de ce lien.

Après l'étape finale, toute source qui reçoit un NO n'est plus une source et devient un puits. Une étape supplémentaire, l' élagage , est également introduite pour supprimer les nœuds qui sont inutiles, c'est-à-dire que leur existence n'a pas d'impact sur les prochaines itérations.

Si un évier est une feuille, alors il est inutile et est donc supprimé.
Si, dans la phase YO, la même valeur est reçue par un nœud de plusieurs voisins internes, il demandera à tous sauf un de supprimer le lien les reliant.

Cette méthode a un coût total de messages O(mlgn). La complexité réelle de son message, y compris l'élagage, est un problème de recherche ouvert et inconnu.

Applications

Réseaux radio

Dans les protocoles de réseau radio, l'élection du leader est souvent utilisée comme première étape pour aborder des primitives de communication plus avancées, telles que la collecte de messages ou les diffusions. La nature même des réseaux sans fil induit des collisions lorsque des nœuds adjacents transmettent en même temps ; l'élection d'un chef permet de mieux coordonner ce processus. Alors que le diamètre D d'un réseau est une limite inférieure naturelle pour le temps nécessaire pour élire un leader, les limites supérieure et inférieure pour le problème d'élection du leader dépendent du modèle radio spécifique étudié.

Modèles et temps d'exécution

Dans les réseaux radio, les n nœuds peuvent à chaque tour choisir de transmettre ou de recevoir un message. Si aucune détection de collision n'est disponible, un nœud ne peut pas faire la distinction entre le silence ou la réception de plus d'un message à la fois. Si la détection de collision est disponible, alors un nœud peut détecter plus d'un message entrant en même temps, même si les messages eux-mêmes ne peuvent pas être décodés dans ce cas. Dans le modèle de bip , les nœuds ne peuvent faire la distinction qu'entre le silence ou au moins un message via la détection de porteuse .

Les temps d'exécution connus pour les réseaux à saut unique vont d'une constante (attendue avec détection de collision) à O(n log n) tours (déterministe et sans détection de collision). Dans les réseaux multi-sauts , les temps d'exécution connus diffèrent d'environ O((D+ log n)(log² log n)) tours (avec une forte probabilité dans le modèle de bip), O(D log n) (déterministe dans le modèle de bip), O (n) (déterministe avec détection de collision) à O(n log ^3/2 n (log log n) ^0,5 ) tours (déterministe et sans détection de collision).

Languages

In other projects