Notes de Cours d'Algorithmique Distribuée
Table des matieres
1 Horloges logiques#
Les systèmes distribués posent une difficulté fondamentale qui n’existe pas dans les systèmes centralisés : en l’absence d’une mémoire partagée et d’une horloge physique commune, il est impossible de savoir, en toute généralité, dans quel ordre absolu se sont produits les événements répartis sur plusieurs processus. Ce chapitre construit, pas à pas, les outils conceptuels qui permettent de raisonner sur le temps dans un système distribué : la relation de causalité de Lamport, les horloges scalaires, et les horloges vectorielles.
1.1 Causalité et relation « happens-before »#
Dans un système distribué, les processus n’ont accès à aucune horloge globale. La seule information temporelle fiable qu’un processus possède est l’ordre dans lequel il a lui-même exécuté ses propres événements. Pour comparer des événements appartenant à des processus différents, il faut donc s’appuyer sur une notion plus abstraite : la causalité, c’est-à-dire la possibilité qu’un événement ait pu influencer un autre.
Un système distribué est un ensemble de processus qui communiquent exclusivement par échange de messages (il n’y a pas de mémoire partagée). Chaque processus possède une histoire locale , c’est-à-dire une séquence totalement ordonnée d’événements : des événements locaux (calculs internes), des envois de messages (send) et des réceptions de messages (receive).
L’ensemble des événements de tous les processus forme l’histoire globale du système. La question centrale est : peut-on définir un ordre partiel sur ces événements qui reflète fidèlement les relations de cause à effet ? C’est précisément ce qu’a proposé Leslie Lamport en 1978 avec la relation « happens-before ».
Définition 2 (Relation happens-before (→)).
La relation happens-before, notée , est le plus petit ordre strict sur les événements du système vérifiant les trois règles suivantes :
-
Ordre local. Si et sont deux événements d’un même processus et que précède dans l’histoire locale de , alors .
-
Communication. Si est l’envoi d’un message et est la réception de ce même message (par un processus éventuellement différent), alors .
-
Transitivité. Si et , alors .
La relation définit un ordre strict partiel sur l’ensemble des événements : elle est irréflexive (aucun événement ne précède lui-même), asymétrique (si alors il est impossible que ) et transitive par construction. Elle ne définit pas un ordre total : deux événements peuvent ne pas être comparables.
Lorsque deux événements ne sont reliés ni dans un sens ni dans l’autre par la relation , on dit qu’ils sont concurrents. Cette notion est fondamentale : elle exprime qu’aucune information ne peut avoir circulé de l’un vers l’autre, et donc que ces deux événements ont pu se produire « simultanément » du point de vue du système.
Définition 3 (Événements concurrents).
Deux événements et sont dits concurrents, noté , si et seulement si
Exemple 1 (Chaîne causale et concurrence).
Considérons trois processus , , . produit un événement , puis envoie un message à . La réception de ce message par constitue l’événement . envoie ensuite un message à , reçu par comme événement . On a donc la chaîne causale
Par transitivité, . Séparément, produit un événement postérieur à dans son histoire locale, mais aucun message ne relie à ou à . On a donc et : ni n’a pu influencer , ni n’a pu influencer .
1.2 Horloges de Lamport (scalaires)#
Disposer d’une relation de causalité est utile sur le plan conceptuel, mais les algorithmes distribués ont souvent besoin de timestamps — des entiers attachés aux événements — qui respectent la causalité et permettent des comparaisons simples. Lamport a proposé à cet effet une construction remarquablement simple : l’horloge logique scalaire.
L’idée directrice est la suivante. Chaque processus maintient un compteur entier qui représente sa vision locale du « temps logique ». Avant tout événement, ce compteur est incrémenté ; lors d’une réception, le compteur est mis à jour pour tenir compte de l’estampille reçue. Ainsi, si un message porte l’estampille , le processus récepteur sait qu’au moins événements ont eu lieu causalement avant cet instant.
La règle de réception garantit que le compteur du processus récepteur dépasse strictement l’estampille du message reçu, ce qui encode le fait que la réception est postérieure à l’envoi.
Théorème 1 (Cohérence des horloges de Lamport).
Pour tout couple d’événements et ,
où désigne l’estampille de Lamport de l’événement .
Preuve 1.
On raisonne par induction sur la définition de .
-
Règle 1 (ordre local). Si et sont deux événements successifs de avec avant , alors a été incrémenté au moins une fois entre et , donc .
-
Règle 2 (communication). Si est l’envoi et la réception du même message, alors , où est la valeur du compteur avant la mise à jour.
-
Règle 3 (transitivité). Si , par hypothèse d’induction et , donc .
Remarque 2 (Limitation fondamentale).
La réciproque du théorème précédent est fausse en général :
Deux événements concurrents peuvent très bien recevoir des estampilles telles que . Les horloges de Lamport permettent de savoir qu’un événement est peut-être antérieur à un autre, mais elles ne permettent pas de détecter la concurrence.
Les horloges de Lamport produisent une extension linéaire de l’ordre partiel causal : elles placent tous les événements sur une droite numérique cohérente avec , mais en « aplatissant » des événements concurrents qui n’avaient aucun lien. C’est suffisant pour certains algorithmes (exclusion mutuelle de Lamport, par exemple), mais insuffisant pour détecter la concurrence ou caractériser exactement la causalité.
Exemple 2 (Trace d'horloge de Lamport).
Considérons deux processus et (compteurs initiaux ).
- produit un événement local : , estampille .
- envoie un message : , estampille attachée .
- produit un autre événement local : , estampille .
- reçoit le message de () : , estampille .
- produit un événement local : , estampille .
On constate que l’événement local de (estampille ) et la réception par (estampille ) sont concurrents, pourtant ils partagent la même valeur d’horloge. La distinction devient impossible avec les seules horloges scalaires.
1.3 Horloges vectorielles (Fidge–Mattern)#
Les horloges de Lamport souffrent d’une asymétrie gênante : elles préservent la causalité dans un sens () mais ne la caractérisent pas dans l’autre. Pour pallier cette limitation, Colin Fidge et Friedemann Mattern ont proposé indépendamment, en 1988, les horloges vectorielles, qui réalisent une équivalence complète entre ordre causal et comparaison d’estampilles.
L’idée clé est que chaque processus ne maintient plus un simple entier, mais un vecteur d’entiers de taille — un par processus. La -ième composante du vecteur de représente le nombre d’événements de dont a connaissance (directement ou par transitvité des messages reçus).
Définition 4 (Horloge vectorielle).
Chaque processus () maintient un vecteur , initialisé à . La composante représente le nombre d’événements du processus que connaît causalement.
L’estampille vectorielle d’un événement exécuté par est la valeur après la mise à jour liée à , notée .
La mise à jour par maximum lors d’une réception est cruciale : elle propage la connaissance causale du processus émetteur vers le processus récepteur. Après la réception, connaît tous les événements que connaissait au moment de l’envoi, ainsi que l’envoi lui-même.
Définition 5 (Ordre componentwise).
Soient deux vecteurs d’estampilles. On définit :
- si et seulement si pour tout .
- si et seulement si et .
- et sont incomparables si ni ni .
Théorème 2 (Caractérisation exacte de la causalité).
Pour tout couple d’événements et ,
Autrement dit, les horloges vectorielles caractérisent exactement la relation happens-before.
Ce résultat est le point fort des horloges vectorielles : contrairement aux horloges de Lamport, la comparaison des estampilles est une condition nécessaire et suffisante pour la causalité. On peut ainsi décider algorithmiquement si deux événements sont dans une relation causale ou s’ils sont concurrents, sans ambiguïté.
Corollaire 1.
Deux événements et sont concurrents si et seulement si leurs estampilles vectorielles sont incomparables :
Le coût des horloges vectorielles est proportionnel au nombre de processus : chaque processus stocke un vecteur de taille , et chaque message transporte également un tel vecteur. Dans les grands systèmes distribués ( de l’ordre de plusieurs milliers), ce surcoût peut devenir prohibitif. Des variantes compressées (horloges matricielles, plumb-bob clocks, etc.) ont été proposées pour réduire ce coût au prix de garanties affaiblies.
Exemple 3 (Trace vectorielle sur trois processus).
Considérons trois processus , , (vecteurs initiaux ). Le déroulement suivant illustre le mécanisme :
- produit : .
- envoie un message à (événement ) : , vecteur attaché au message.
- reçoit le message () : , puis .
- envoie un message à (, avec ) : , vecteur attaché.
- reçoit le message () : , puis .
- produit un événement indépendant (pas de message) : .
Vérification :
- (componentwise) . ✓
- et : mais , donc les vecteurs sont incomparables . ✓
2 Algorithmes de diffusion#
Dans un système distribué, les nœuds ne partagent pas de mémoire commune et ne peuvent communiquer qu’en échangeant des messages via les canaux du réseau. L’une des opérations fondamentales est la diffusion (broadcast) : un nœud initiateur souhaite transmettre une information à l’ensemble des nœuds du réseau. Ce chapitre étudie plusieurs algorithmes permettant d’accomplir cette tâche, en analysant leur correction, leur complexité en messages et en temps, ainsi que la question de la détection de terminaison globale.
On suppose tout au long de ce chapitre que le réseau est modélisé par un graphe connexe non orienté , où désigne le nombre de nœuds et le nombre d’arêtes. Les canaux de communication sont supposés fiables (pas de perte de message) et FIFO.
2.1 Diffusion de base : inondation#
2.1.1 Formulation du problème#
Avant de présenter l’algorithme, précisons le problème que nous cherchons à résoudre.
Étant donné un réseau connexe et un nœud initiateur qui détient une valeur , le problème de diffusion consiste à concevoir un algorithme distribué garantissant que tout nœud reçoit finalement la valeur , même si les nœuds n’ont aucune connaissance préalable de la topologie du réseau.
2.1.2 L’algorithme d’inondation#
L’idée centrale de l’inondation (flooding) est d’une simplicité remarquable : chaque nœud, dès la première réception du message, le retransmet à tous ses voisins. Les messages en double (reçus par un nœud déjà informé) sont silencieusement ignorés.
Proposition 1 (Correction de l'inondation).
Si le graphe est connexe, alors l’algorithme d’inondation garantit que tout nœud reçoit le message en temps fini.
Preuve. Puisque est connexe, il existe un chemin entre l’initiateur et tout nœud . On montre par induction sur que reçoit le message. L’initiateur envoie à tous ses voisins, en particulier à ; reçoit donc et, étant alors non informé, le retransmet à ses voisins, dont ; et ainsi de suite. Le nœud reçoit ainsi à l’étape .
Proposition 2 (Complexité de l'inondation).
L’algorithme d’inondation satisfait les bornes de complexité suivantes :
- Messages : au plus messages sont échangés au total. En pratique, chaque arête peut porter au plus un message dans chaque direction : lorsque informe et que rétransmet à , ce dernier message est simplement ignoré. Donc le nombre de messages est exactement le nombre d’arêtes du réseau couvertes par la diffusion, multiplié par 2, soit .
- Temps : la diffusion se termine en unités de temps, où est le diamètre du graphe (longueur maximale d’un plus court chemin entre deux nœuds). En effet, chaque nœud à distance de l’initiateur reçoit le message au plus tours après le départ.
La règle d’ignorer les messages dupliqués est essentielle pour la terminaison. Sans elle, un nœud pourrait retransmettre indéfiniment des messages reçus par des chemins différents, créant des boucles de diffusion. Le booléen joue exactement le rôle de garde-fou contre cette situation.
2.1.3 Exemple : réseau à 4 nœuds#
Exemple 4 (Trace d'inondation sur 4 nœuds).
Considérons le graphe avec et les arêtes . L’initiateur est .
- Tour 1. se marque informé et envoie à et (ses deux voisins).
- Tour 2. reçoit de : se marque informé, retransmet à et (en excluant ). reçoit de : se marque informé, retransmet à et (en excluant ).
- Tour 3. reçoit de (et/ou de ) : se marque informé, aucune retransmission utile. reçoit de : déjà informé, ignore. reçoit de : déjà informé, ignore.
Au final, 4 messages utiles sont échangés (, , , ) et 2 messages dupliqués ( et ) sont ignorés. On a bien arêtes et au plus messages possibles ; ici seulement 6 sont effectivement envoyés.
2.2 Diffusion sur arbre couvrant#
2.2.1 Motivation#
L’algorithme d’inondation, bien que simple et robuste, souffre d’un défaut : il génère des messages redondants (les doublons ignorés représentent un gaspillage de bande passante). Si le réseau dispose d’un arbre couvrant pré-calculé enraciné en l’initiateur, on peut diffuser de manière bien plus économique, sans aucun doublon.
Un arbre couvrant de est un sous-graphe qui est un arbre (connexe et acyclique) et qui contient tous les nœuds de . Tout graphe connexe admet au moins un arbre couvrant.
2.2.2 L’algorithme de diffusion sur arbre#
Théorème 3 (Optimalité de la diffusion sur arbre).
Tout algorithme distribué de diffusion dans un réseau à nœuds doit envoyer au moins messages. La diffusion sur arbre couvrant est donc optimale en nombre de messages, car elle en envoie exactement .
Preuve. Considérons l’état initial : seul l’initiateur détient le message . Pour qu’un nœud reçoive , il doit recevoir au moins un message le contenant (ou le permettant de le reconstruire). Ces réceptions doivent être distinctes : si on supprime tous les messages envoyés, aucun nœud sauf ne peut être informé. Il faut donc au moins un message par nœud non-initiateur, soit messages au minimum.
La diffusion sur arbre envoie exactement un message par arête de l’arbre, soit messages (un arbre à nœuds a arêtes). L’algorithme est donc optimal.
La diffusion sur arbre suppose que l’arbre couvrant est connu à l’avance par tous les nœuds participants. En pratique, il faut donc d’abord exécuter un algorithme de construction d’arbre couvrant (voir Chapitre 3). Le coût total inclut alors la construction de l’arbre plus la diffusion elle-même. Néanmoins, si l’arbre peut être réutilisé pour plusieurs diffusions successives, l’investissement initial est largement amorti.
2.3 Détection de terminaison par vague d’acquittements#
2.3.1 Le problème de terminaison#
La diffusion sur arbre garantit que tous les nœuds reçoivent le message en exactement messages. Cependant, un problème pratique demeure : l’initiateur ne sait pas quand la diffusion est terminée. Il sait qu’il a envoyé ses messages, mais il n’a aucune information sur le moment où le dernier nœud a été informé. Ce problème est particulièrement aigu lorsque la diffusion sert à déclencher une action distribuée et que l’initiateur doit attendre la fin de cette action avant de continuer.
On dit que la diffusion est globalement terminée au moment où le dernier nœud a reçu et traité le message . La détection de terminaison consiste à permettre à l’initiateur (ou à un observateur désigné) de savoir avec certitude quand cet instant est atteint.
2.3.2 La vague d’acquittements#
La solution classique repose sur une deuxième phase qui remonte l’arbre en sens inverse sous forme d’acquittements (ACK). L’invariant fondamental est le suivant : un nœud envoie un ACK à son père si et seulement si lui-même a reçu le message et tous les nœuds du sous-arbre enraciné en l’ont également reçu.
Théorème 4 (Correction de la vague d'acquittements).
Lorsque l’initiateur reçoit un ACK de tous ses fils, la diffusion est effectivement terminée, c’est-à-dire que tout nœud a reçu et traité le message .
Preuve. On montre par induction structurelle sur l’arbre que, pour tout nœud , le nœud envoie un ACK à son père si et seulement si (a) a reçu et (b) tous les nœuds du sous-arbre enraciné en ont reçu .
-
Base. Pour une feuille : . La feuille envoie un ACK dès qu’elle reçoit ; il n’y a pas de sous-arbre non trivial. La propriété est vérifiée.
-
Induction. Soit un nœud interne de fils . Par hypothèse d’induction, envoie un ACK à si et seulement si tout le sous-arbre a reçu . Le nœud attend les ACKs de tous ses fils, donc il envoie un ACK à son père si et seulement si a reçu ET ont tous reçu , ce qui est exactement tout entier.
À la racine, tout entier. Donc quand reçoit les ACKs de tous ses fils, tout entier a reçu .
Proposition 3 (Complexité de la vague d'acquittements).
La vague d’acquittements utilise exactement messages au total :
- messages lors de la phase de descente (un par arête de l’arbre, descendante).
- messages lors de la phase de remontée (un ACK par arête de l’arbre, montante).
Le temps de terminaison est où est la hauteur de l’arbre, car la descente et la remontée parcourent chacune au maximum niveaux.
Ce schéma de diffusion suivie d’une vague d’acquittements est extrêmement général. Il peut être adapté à n’importe quel calcul distribué sur arbre : chaque nœud peut effectuer un calcul local et remonter un résultat (par exemple une somme, un minimum, un vote) plutôt qu’un simple ACK. On parle alors de réduction distribuée (distributed reduce), qui constitue la brique fondamentale de nombreux algorithmes parallèles et distribués.
3 Construction d’arbres couvrants#
Les arbres couvrants occupent une place centrale dans les algorithmes distribués. Comme nous l’avons vu au chapitre précédent, disposer d’un arbre couvrant permet d’effectuer des diffusions optimales en messages et d’organiser des calculs collectifs (réductions, vagues d’acquittements) de manière structurée. Ce chapitre étudie comment construire un tel arbre de façon distribuée, c’est-à-dire sans qu’aucun nœud ne connaisse à l’avance la topologie globale du réseau.
Nous présentons trois familles d’approches aux caractéristiques très différentes :
- L’exploration séquentielle par jeton DFS, qui visite les nœuds un par un avec une garantie de profondeur ;
- L’exploration parallèle par inondation BFS, qui construit un arbre de plus courts chemins très rapidement ;
- Les vagues synchronisées de Bellman-Ford, qui généralisent aux graphes pondérés.
On suppose dans tout ce chapitre que le réseau est modélisé par un graphe connexe non orienté avec et .
Définition 8 (Arbre couvrant).
Un arbre couvrant (spanning tree) de est un sous-graphe tel que :
- (les arêtes de sont des arêtes de ) ;
- est connexe ;
- est acyclique.
Tout graphe connexe admet au moins un arbre couvrant. Un arbre couvrant à nœuds possède exactement arêtes.
Étant donné une racine , on parle d’arbre couvrant enraciné : chaque nœud possède un unique parent sur le chemin de à dans , et les nœuds directement reliés à en dessous de sont ses fils.
3.1 Exploration séquentielle : parcours en profondeur avec jeton#
3.1.1 Motivation#
L’approche la plus intuitive consiste à simuler un parcours en profondeur (DFS — Depth-First Search) de manière distribuée. Un jeton (token) physique circule dans le réseau ; à tout instant, exactement un nœud détient le jeton, ce qui garantit une exploration séquentielle sans conflits. Cette approche est particulièrement utile lorsque l’on doit visiter chaque nœud exactement une fois (par exemple pour compter les nœuds, vérifier une propriété globale, ou construire un identifiant unique pour chaque nœud).
3.1.2 L’algorithme DFS avec jeton#
Théorème 5 (Correction du DFS distribué).
À la fin de l’algorithme DFS avec jeton, le graphe où est un arbre couvrant de enraciné en , et il s’agit d’un arbre DFS.
Preuve (esquisse). On montre par invariant que le jeton ne visite jamais un nœud déjà intégré dans l’arbre via le même chemin. Chaque nœud est visité au plus une fois (le booléen l’empêche d’être intégré deux fois). Comme est connexe, tous les nœuds sont atteignables depuis et seront éventuellement visités. L’absence de cycle résulte du fait que les arêtes de l’arbre vont toujours de parent à fils.
Proposition 4 (Complexité du DFS distribué).
L’algorithme DFS avec jeton satisfait les bornes suivantes :
- Messages : exactement messages, où . En effet, chaque arête est traversée exactement deux fois par le jeton : une fois dans chaque direction (aller et retour). Les arêtes de l’arbre sont traversées une fois vers l’avant (arête arbre DFS) et une fois en retour arrière ; les arêtes non-arbre sont traversées immédiatement en retour (car le nœud visité renvoie le jeton aussitôt).
- Temps : étapes de communication (séquentiel — le jeton parcourt toutes les arêtes une par une).
- Caractère séquentiel : à tout instant, un seul nœud est actif (celui qui détient le jeton). Cela simplifie certaines propriétés de sécurité mais peut être lent sur de grands graphes.
Exemple 5 (Trace DFS sur 4 nœuds).
Considérons avec les arêtes , , , , , (graphe complet ). L’initiateur est .
- Étape 1 : envoie le jeton à . Arête arbre : .
- Étape 2 : (non visité) enregistre , envoie le jeton à . Arête arbre : .
- Étape 3 : (non visité) enregistre , envoie le jeton à . Arête arbre : .
- Étape 4 : (non visité) enregistre . n’a plus de voisins non visités (tous déjà marqués). Retour arrière : .
- Étape 5 : reçoit le jeton en retour, plus de voisins non visités. Retour arrière : .
- Étape 6 : reçoit le jeton en retour, plus de voisins non visités. Retour arrière : .
- Étape 7 : reçoit le jeton. Plus de voisins non visités. DFS terminé.
Arbre DFS construit : (chemin). Total : messages pour arêtes de .
3.2 Exploration parallèle : BFS par inondation#
3.2.1 Motivation#
L’algorithme DFS est séquentiel : la progression est lente car le jeton visite les nœuds un à un. Dans de nombreuses applications, on préfère exploiter le parallélisme inhérent au réseau pour construire l’arbre couvrant le plus rapidement possible. L’approche par inondation BFS (Breadth-First Search) atteint cet objectif : tous les voisins de l’initiateur sont explorés simultanément, puis tous leurs voisins, etc.
3.2.2 L’algorithme BFS par inondation#
Théorème 6 (L'arbre résultant est un arbre BFS).
À la fin de l’algorithme BFS par inondation, le sous-graphe des arêtes est un arbre couvrant BFS de enraciné en : pour tout nœud , la distance dans entre et est égale à la distance dans (en nombre de sauts).
Preuve. Montrons que le premier message reçu par arrive par un voisin situé à distance de , ce qui garantit que est sur un plus court chemin de à .
On procède par récurrence sur . Si , est voisin de et reçoit le message directement de au premier tour. Supposons la propriété vraie pour tout nœud à distance . Un nœud à distance est voisin d’au moins un nœud à distance . Par hypothèse d’induction, a été visité au tour et envoie le message au tour . Aucun nœud plus proche ne peut envoyer de message à avant le tour (car ils n’ont été visités qu’à partir du tour ). Donc est visité au tour par un nœud à distance , ce qui est bien un plus court chemin.
Proposition 5 (Complexité du BFS par inondation).
L’algorithme BFS par inondation satisfait :
- Messages : . Chaque arête porte au plus deux messages : un dans chaque direction (l’un des deux est toujours ignoré).
- Temps : tours de communication. Chaque nœud à distance de la racine est visité au tour , et le nœud le plus éloigné est à distance .
Contrairement au DFS, le BFS par inondation est entièrement parallèle : plusieurs nœuds peuvent être actifs simultanément. En conséquence, le temps de construction est considérablement réduit — au lieu de — mais le nombre de messages reste similaire. En pratique, sur des réseaux à faible diamètre (par exemple des graphes expanders), le BFS est beaucoup plus rapide que le DFS. En revanche, le BFS ne garantit pas l’ordre de visite des nœuds au sein d’un même niveau, ce qui peut être une limitation pour certaines applications.
3.3 Vagues synchronisées : Bellman-Ford distribué#
3.3.1 Motivation#
Les deux algorithmes précédents construisent un arbre couvrant quelconque (DFS) ou un arbre de plus courts chemins en nombre de sauts (BFS). Cependant, dans de nombreuses applications réelles, les arêtes du réseau ont des poids (latences, débits, coûts) et l’on souhaite construire un arbre de plus courts chemins pondérés. C’est l’objectif de l’algorithme de Bellman-Ford distribué.
3.3.2 L’algorithme Bellman-Ford distribué#
Soit un graphe connexe pondéré (avec poids pour toute arête ). On cherche à construire un arbre couvrant enraciné en où la distance de à tout nœud est minimale.
Théorème 7 (Convergence de Bellman-Ford distribué).
L’algorithme Bellman-Ford distribué converge en au plus tours. À la convergence, pour tout nœud , est égal à la distance pondérée minimale entre et dans .
Preuve. On montre par récurrence sur qu’après tours, pour tout chemin de longueur , on a .
- Base () : . Correct.
- Hérédité : Au tour , le nœud reçoit de chaque voisin . Par hypothèse, est au plus le poids du plus court chemin de longueur de à . Alors est au plus le poids d’un chemin de longueur de à via . En prenant le minimum sur tous les voisins, atteint le poids du plus court chemin de longueur .
Tout plus court chemin (sans cycle, puisque les poids sont positifs) comporte au plus arêtes. Donc après tours, toutes les distances sont convergeantes.
Proposition 6 (Complexité de Bellman-Ford distribué).
L’algorithme Bellman-Ford distribué satisfait :
- Messages : . À chaque tour, chaque nœud envoie un message à chacun de ses voisins, soit messages par tour. Sur tours : messages au total.
- Temps : tours de communication.
- Résultat : arbre couvrant de plus courts chemins pondérés depuis .
Dans le cas non pondéré (tous les poids égaux à 1), l’algorithme Bellman-Ford distribué produit le même résultat que le BFS par inondation, mais en tours au lieu de . Le BFS est donc préférable pour les graphes non pondérés.
L’algorithme de Bellman-Ford distribué est à la base du protocole de routage RIP (Routing Information Protocol), l’un des premiers protocoles de routage Internet. Dans ce contexte, les nœuds sont des routeurs, les arêtes sont des liens réseau avec des métriques (nombre de sauts, latences), et chaque routeur calcule sa table de routage en exécutant Bellman-Ford de manière continue. La convergence lente ( tours dans le pire cas) est l’une des limitations connues de RIP, surtout en présence de pannes (le phénomène de « count to infinity »).
3.4 Tableau comparatif des algorithmes de construction#
| Algorithme | Messages | Temps | Résultat | Particularité |
|---|---|---|---|---|
| DFS avec jeton | Arbre DFS | Séquentiel ; visite chaque arête exactement deux fois ; garantit un ordre DFS | ||
| BFS par inondation | Arbre BFS (plus courts chemins en sauts) | Parallèle ; très rapide ; ne gère pas les poids | ||
| Bellman-Ford distribué | Arbre de plus courts chemins pondérés | Gère les poids ; lent ; base de RIP |
En résumé, le choix de l’algorithme dépend du contexte applicatif :
- Si l’on souhaite un arbre de façon séquentielle et garantie, le DFS avec jeton est simple et robuste.
- Si la rapidité de construction est prioritaire et le graphe non pondéré, le BFS par inondation est optimal en temps.
- Si le réseau est pondéré et que l’on a besoin de plus courts chemins, Bellman-Ford distribué est le choix naturel, au prix d’un plus grand nombre de messages.
4 Exclusion mutuelle distribuée#
Dans un système à mémoire partagée, l’exclusion mutuelle s’obtient facilement grâce à des primitives comme les sémaphores ou les verrous matériels. La situation est radicalement différente dans un système distribué : il n’existe aucune mémoire commune, et les processus ne communiquent qu’en s’échangeant des messages. Le problème de l’exclusion mutuelle distribuée consiste à garantir qu’au plus un processus à la fois exécute une section critique (SC), c’est-à-dire un fragment de code accédant à une ressource partagée.
Ce chapitre présente cinq approches classiques, du plus simple au plus élaboré. Chacune réalise un compromis entre le nombre de messages échangés par entrée en SC, la robustesse aux pannes et la complexité de mise en œuvre.
Définition 9 (Section critique et exclusion mutuelle distribuée).
Soit processus se partageant une ressource. On dit qu’un protocole d’exclusion mutuelle est correct s’il satisfait simultanément :
- Sûreté : à tout instant, au plus un processus se trouve en section critique.
- Vivacité : toute demande d’entrée en SC est éventuellement accordée (absence d’interblocage et d’attente infinie).
- Équité : les demandes sont traitées dans un ordre juste, idéalement FIFO selon leurs horodatages.
La métrique standard pour comparer ces algorithmes est le nombre de messages échangés par entrée en SC.
4.1 Solution centralisée#
La solution la plus immédiate est d’élire un processus coordinateur qui gère l’accès à la ressource. Lorsque souhaite entrer en SC, il envoie une requête au coordinateur. Celui-ci maintient une file d’attente des demandes en suspens et accorde l’accès selon l’ordre FIFO. Quand a terminé, il notifie le coordinateur par un message de libération.
Cette approche nécessite trois messages par entrée en SC, indépendamment du nombre de processus. Elle est donc extrêmement économique en termes de communication. En revanche, elle crée un point unique de défaillance : si le coordinateur tombe en panne, tout le système est bloqué. De plus, le coordinateur devient un goulot d’étranglement à mesure que le nombre de processus croît.
Proposition 7 (Complexité de la solution centralisée).
La solution centralisée nécessite exactement 3 messages par entrée en SC :
- 1 message de vers le coordinateur,
- 1 message du coordinateur vers ,
- 1 message de vers le coordinateur.
L’algorithme centralisé est correct (sûreté et vivacité garanties par la gestion FIFO de la file). Cependant, son déploiement suppose qu’un coordinateur ait préalablement été élu — ce qui est lui-même un problème non trivial dans un système distribué (voir Chapitre 6). La panne du coordinateur nécessite un mécanisme de recouvrement.
4.2 Algorithme de Lamport (1978)#
L’algorithme de Lamport est la première solution entièrement distribuée à l’exclusion mutuelle. Chaque processus maintient une file locale des demandes en cours, ordonnée par les horodatages de Lamport. L’idée centrale est que chaque processus peut calculer localement quel processus a la priorité, à condition d’avoir connaissance de toutes les demandes en circulation.
Pour entrer en SC, diffuse sa demande à tous les processus et attend deux conditions : (a) sa demande est minimale dans toutes les files locales, et (b) il a reçu un accusé de réception de chaque autre processus postérieur à sa propre demande. La sortie est également diffusée afin que tous les processus retirent la demande de leurs files.
Théorème 8 (Correction de l'algorithme de Lamport).
L’algorithme de Lamport satisfait les propriétés de sûreté, de vivacité et d’équité (ordre FIFO par horodatage).
Sûreté : Supposons par l’absurde que et soient simultanément en SC, avec (ou et ). Alors . Lorsque entre en SC, il doit avoir reçu un message de postérieur à , donc a déjà reçu l’accusé de réception de — mais cela est impossible si est entré avant d’avoir acquitté .
Vivacité : Le bon ordre de la file et la propagation des ACK garantissent qu’aucune demande ne reste bloquée indéfiniment, en l’absence de panne.
Proposition 8 (Complexité de l'algorithme de Lamport).
L’algorithme de Lamport nécessite messages par entrée en SC :
- Phase 1 (diffusion DEMANDE) : messages,
- Phase 2 (ACK) : messages,
- Phase 3 (diffusion SORTIE) : messages.
La phase de sortie est coûteuse : diffuser à processus n’est nécessaire que pour maintenir les files cohérentes. Ricart et Agrawala ont observé que cette phase pouvait être éliminée grâce aux réponses différées.
4.3 Algorithme de Ricart et Agrawala (1981)#
L’algorithme de Ricart et Agrawala optimise celui de Lamport en supprimant la diffusion de sortie. L’idée clé est la suivante : lorsqu’un processus est en SC (ou a une demande prioritaire), il diffère sa réponse aux demandes concurrentes. Quand sort de la SC, il envoie directement ses réponses différées — ce qui revient implicitement à notifier les processus concernés sans diffusion globale.
Deux processus et ont des priorités comparables via leurs horodatages : la demande avec le plus petit horodatage (et, à égalité, le plus petit identifiant) est prioritaire. Si reçoit la demande de et que est prioritaire, il diffère sa réponse jusqu’à sa propre sortie de SC. Sinon, il répond immédiatement.
Théorème 9 (Correction de Ricart-Agrawala).
L’algorithme de Ricart-Agrawala satisfait la sûreté et la vivacité.
Sûreté : Si et demandent la SC simultanément avec , alors recevra le de et répondra immédiatement (car est prioritaire), mais ne répondra à qu’après sa sortie de SC. Donc ne pourra pas entrer avant , et a fortiori pas en même temps.
Vivacité : En l’absence de panne, les réponses différées sont toujours finalement envoyées, garantissant la progression.
Proposition 9 (Complexité de Ricart-Agrawala).
L’algorithme de Ricart-Agrawala nécessite messages par entrée en SC :
- Phase 1 (diffusion REQ) : messages,
- Phase 2 (réponses OK, immédiates ou différées) : messages.
Gain par rapport à Lamport : messages (la phase SORTIE est supprimée).
4.4 Ricart-Agrawala avec jeton explicite#
Les deux algorithmes précédents sont dits sans jeton : chaque processus décide localement de son droit d’entrée. Une variante populaire utilise un jeton (token) matérialisant explicitement le droit d’accès. Un seul jeton existe dans le système ; le posséder est une condition nécessaire et suffisante pour entrer en SC.
Le jeton est un tableau de taille où enregistre le nombre de fois que est entré en SC depuis la création du jeton. Chaque maintient également un tableau de demandes où est le numéro de séquence de la dernière demande de .
Proposition 10 (Complexité de R-A avec jeton).
L’algorithme R-A avec jeton nécessite au plus messages par entrée en SC :
- messages pour la diffusion de la demande,
- 1 message pour le transfert du jeton (depuis son détenteur actuel),
- éventuellement des transferts successifs si le détenteur actuel passe le jeton (au plus sauts).
Dans le meilleur cas (jeton disponible immédiatement), le coût est de messages.
L’utilisation d’un jeton apporte une simplification conceptuelle importante : la décision d’entrer en SC est binaire (posséder ou non le jeton). En revanche, la perte du jeton (due à une panne du processus le détenant) est catastrophique et nécessite un protocole de régénération spécifique.
4.5 Anneau à jeton#
L’anneau à jeton est une solution élégante qui organise les processus en anneau logique . Un unique jeton circule en permanence dans cet anneau dans le sens des aiguilles d’une montre. Lorsqu’un processus reçoit le jeton, il peut l’utiliser pour entrer en SC ; s’il n’en a pas besoin, il le transfère immédiatement au processus suivant.
Cette approche est remarquable par sa simplicité : il n’y a aucune négociation ni aucun calcul de priorité. L’équité est garantie naturellement puisque le jeton fait le tour de tous les processus à chaque cycle. Le coût varie selon la position relative du jeton au moment de la demande.
Proposition 11 (Complexité de l'anneau à jeton).
- Meilleur cas : 0 message par entrée en SC (le jeton arrive exactement au bon moment).
- Pire cas : messages par entrée en SC (le jeton vient d’être transmis au processus suivant, et doit faire presque tout le tour).
- En moyenne : messages par entrée en SC.
L’anneau à jeton génère du trafic en permanence, même si aucun processus ne souhaite la SC. Si processus utilisent fréquemment la SC, la circulation continue du jeton peut être avantageuse ; si les demandes sont rares, ce trafic de fond constitue un gaspillage. La perte du jeton (panne d’un processus en transit) exige un protocole de détection et de régénération.
4.6 Comparaison des algorithmes#
Il existe un compromis fondamental entre le nombre de messages par entrée en SC et le degré de distribution du contrôle. La solution centralisée est la moins coûteuse en messages (3 par entrée) mais crée un point de défaillance unique. Les solutions distribuées comme Lamport et Ricart-Agrawala nécessitent messages mais offrent une meilleure tolérance aux pannes. Le jeton (implicite ou explicite) représente un compromis intermédiaire.
| Algorithme | Messages/entrée | Centralisé ? | Tolérance aux pannes |
|---|---|---|---|
| Centralisée | 3 | Oui | Faible (SPOF) |
| Lamport | Non | Moyenne | |
| Ricart-Agrawala | Non | Moyenne | |
| R-A avec jeton | Non | Perte du jeton | |
| Anneau à jeton | Non | Perte du jeton |
Pour grand, le coût linéaire en des algorithmes distribués peut devenir prohibitif. Des solutions avancées basées sur des structures en arbre ou en quorum permettent de réduire ce coût à ou messages, au prix d’une complexité accrue de mise en œuvre.
5 Tolérance aux pannes#
Tout système distribué réel est soumis à des défaillances : un processus peut s’arrêter inopinément, un lien réseau peut perdre des paquets, ou un composant peut adopter un comportement erroné. La tolérance aux pannes désigne la capacité d’un système à continuer de fonctionner correctement — ou du moins à dégrader gracieusement son service — en présence de telles défaillances.
La question centrale est la suivante : combien de processus défaillants un système distribué peut-il tolérer tout en continuant à garantir ses propriétés ? La réponse dépend crucialement du modèle de panne adopté. Ce chapitre présente une hiérarchie de modèles de pannes, de la plus bénigne à la plus sévère, ainsi que les techniques de redondance permettant de les tolérer.
5.1 Types de pannes#
Les modèles de pannes forment une hiérarchie d’inclusion : les pannes les plus graves englobent les moins graves. Un algorithme conçu pour tolérer des pannes byzantines tolère automatiquement les pannes par omission et par crash.
5.1.1 Pannes par crash#
La panne par crash est le modèle le plus simple et le plus étudié. Un processus qui tombe en panne par crash cesse immédiatement d’envoyer et de recevoir des messages, et ne reprend jamais son exécution (dans le modèle sans recouvrement). L’absence de messages peut être interprétée comme un signal de panne, ce qui rend ce type de défaillance relativement facile à gérer.
Un processus subit une panne par crash si, à partir d’un certain instant , n’envoie plus aucun message et ne traite plus aucun message reçu. Les messages envoyés avant peuvent avoir été ou non reçus par leurs destinataires.
Dans un système asynchrone pur, il est impossible de distinguer un processus en panne par crash d’un processus simplement lent. C’est pourquoi les détecteurs de pannes (basés sur des timeouts) sont souvent utilisés pour approximer cette distinction, au prix d’une possible erreur.
5.1.2 Pannes par omission#
Une panne par omission est plus subtile : le processus continue d’exécuter son code, mais perd parfois des messages à l’émission ou à la réception. Un processus défaillant par omission semble vivant mais est peu fiable.
Définition 11 (Panne par omission).
Un processus subit une panne par omission s’il omet d’envoyer ou de recevoir certains messages. On distingue :
- Omission à l’émission : devrait envoyer un message mais ne le fait pas.
- Omission à la réception : devrait recevoir un message mais ne le traite pas.
- Omission générale : les deux types peuvent se produire.
Toute panne par crash est un cas particulier de panne par omission (toutes les émissions et réceptions sont omises à partir d’un certain moment).
Les pannes par omission modélisent notamment les pertes de paquets dans des réseaux non fiables, les tampons d’émission saturés, ou les problèmes transitoires de connectivité.
5.1.3 Pannes byzantines#
Les pannes byzantines, introduites par Lamport, Shostak et Pease, représentent le cas le plus général et le plus difficile. Un processus byzantin peut se comporter de manière totalement arbitraire : envoyer des valeurs incorrectes, envoyer des valeurs différentes à des destinataires différents, ou se coordonner avec d’autres processus défaillants pour tromper les processus corrects.
Définition 12 (Panne byzantine (faute arbitraire)).
Un processus subit une panne byzantine s’il s’écarte arbitrairement de son comportement spécifié. Formellement, un processus byzantin peut :
- envoyer des messages avec des valeurs incorrectes,
- envoyer des messages différents à différents processus pour la même étape du protocole,
- ne pas envoyer de messages qu’il devrait envoyer,
- envoyer des messages non prévus par le protocole,
- se coordonner avec d’autres processus défaillants.
Théorème 10 (Hiérarchie des modèles de pannes).
Les ensembles de comportements de pannes satisfont :
Cette inclusion est stricte : il existe des comportements d’omission qui ne sont pas des crashes (processus vivant mais perdant des messages), et des comportements byzantins qui ne sont pas des omissions (envoi de valeurs fausses).
5.1.4 Seuils de tolérance#
Le nombre de processus défaillants qu’un système peut tolérer tout en garantissant ses propriétés dépend du modèle de panne et de la propriété souhaitée.
Théorème 11 (Seuils minimaux de tolérance aux pannes).
Pour un système distribué de processus devant tolérer processus défaillants :
-
Tolérance aux crashes : il suffit de processus (mais la disponibilité nécessite souvent pour permettre la prise de décision majoritaire).
-
Tolérance aux pannes byzantines : il est nécessaire et suffisant d’avoir processus. Avec processus, il n’existe aucun protocole capable de garantir l’accord en présence de processus byzantins.
La borne pour les pannes byzantines est fondamentale. Son intuition est la suivante : un groupe de processus byzantins peut se faire passer pour processus corrects tout en envoyant des informations contradictoires aux processus restants. Pour que ces derniers puissent se mettre d’accord malgré tout, il faut que le groupe des corrects soit suffisamment grand (, soit ).
Si , il n’existe pas de protocole d’accord distribué (consensus, broadcast fiable, etc.) tolérant pannes byzantines. Ce résultat est prouvé par un argument de partition : les processus byzantins peuvent partitionner les processus corrects en deux groupes qui reçoivent des informations incompatibles, sans que les corrects puissent les distinguer des byzantins.
5.2 Redondance et réplication#
Face aux pannes, la technique fondamentale est la redondance : maintenir plusieurs copies (répliques) de l’état et de la logique de traitement, de sorte qu’une panne isolée ne compromette pas l’ensemble du système. Deux grandes stratégies de réplication existent.
5.2.1 Réplication active#
Dans la réplication active, toutes les répliques traitent chaque requête et maintiennent le même état. Les clients envoient leurs requêtes à toutes les répliques, et une décision de majorité est prise sur les réponses. Cette approche garantit une disponibilité maximale mais génère un trafic important.
La réplication active requiert que toutes les répliques traitent les requêtes dans le même ordre total. Garantir cet ordre est lui-même un problème non trivial, résolu par des protocoles de diffusion atomique (voir le chapitre sur le consensus).
5.2.2 Réplication passive (primaire-sauvegarde)#
Dans la réplication passive, une seule réplique — le primaire — traite activement les requêtes. Les autres répliques (sauvegardes) reçoivent périodiquement l’état du primaire (points de reprise ou checkpoints). En cas de panne du primaire, une sauvegarde prend le relais.
La réplication passive génère moins de trafic que la réplication active (les sauvegardes ne traitent pas les requêtes). En contrepartie, le temps de reprise après panne peut être non négligeable (durée de l’élection + application des mises à jour manquantes depuis le dernier checkpoint). Elle tolère bien les pannes par crash mais est inadaptée aux pannes byzantines (le primaire peut envoyer des checkpoints falsifiés).
5.2.3 Synchronisation après recouvrement#
Un nœud qui se remet d’une panne doit resynchroniser son état avec les nœuds corrects avant de reprendre sa participation normale au protocole. Cette phase de récupération est délicate :
Le contexte du théorème CAP (Cohérence, Disponibilité, Tolérance aux Partitions) est pertinent ici : dans un système distribué sujet aux partitions réseau, il est impossible de garantir simultanément la cohérence forte et la disponibilité totale. La tolérance aux pannes impose donc des compromis, formalisés dans la pratique par des niveaux de cohérence variés (cohérence finale, lecture de ma propre écriture, etc.).
5.3 Récapitulatif#
Les différents modèles de pannes imposent des contraintes croissantes sur les algorithmes distribués. Tolérer des pannes byzantines est significativement plus coûteux que tolérer des crashes, tant en termes de nombre de processus nécessaires ( contre ) qu’en termes de complexité des protocoles. En pratique, les systèmes choisissent leur modèle de panne en fonction des menaces réelles : les pannes par crash suffisent dans un datacenter de confiance, tandis que les pannes byzantines sont nécessaires pour des systèmes ouverts ou adversariaux (blockchain, etc.).
La redondance est le seul mécanisme universel de tolérance aux pannes. Plus le modèle de panne est sévère, plus la redondance requise est importante. Cependant, la redondance introduit de nouveaux défis : cohérence des répliques, synchronisation après recouvrement, et gestion des partitions réseau. La conception d’un système tolérant aux pannes consiste essentiellement à trouver le bon équilibre entre redondance, performance et complexité.
6 Élection de chef#
Dans de nombreux algorithmes distribués, il est commode de disposer d’un processus particulier jouant le rôle de coordinateur ou de chef : il peut centraliser les décisions, initier un protocole, ou servir de point de synchronisation. Or, dans un système distribué symétrique, tous les processus démarrent dans le même état ; aucun ne joue de rôle privilégié a priori.
Le problème de l’élection de chef consiste à faire converger un système distribué vers un état dans lequel exactement un processus se déclare élu, et tous les autres processus reconnaissent ce choix. La seule hypothèse permettant de briser la symétrie est l’existence d’identifiants uniques pour les processus.
Définition 13 (Problème de l'élection de chef).
Soit un réseau de processus , chacun possédant un identifiant unique . Un algorithme d’élection est correct s’il garantit, à partir de tout état initial :
- Terminaison : en temps fini, tous les processus terminent.
- Accord : exactement un processus se trouve dans l’état « élu ».
- Validité : le processus élu est celui ayant le plus grand (ou le plus petit) identifiant parmi tous les processus corrects.
Les deux algorithmes classiques présentés dans ce chapitre s’appliquent à des topologies en anneau, où les processus sont disposés en cercle et communiquent avec leurs voisins.
6.1 Algorithme de Chang-Roberts (extinction sélective)#
L’algorithme de Chang et Roberts, publié en 1979, s’applique à un anneau unidirectionnel : chaque processus ne peut envoyer des messages que dans un sens (par exemple, dans le sens des aiguilles d’une montre). Le principe est celui de l’extinction sélective : chaque processus envoie son identifiant dans l’anneau, et un identifiant est éliminé dès qu’il rencontre un processus avec un identifiant plus grand. Seul l’identifiant maximal survit et fait le tour complet de l’anneau, désignant son émetteur comme chef.
Théorème 12 (Correction de Chang-Roberts).
L’algorithme de Chang-Roberts est correct : il termine, élit exactement un processus, et ce processus est celui ayant l’identifiant maximal.
Preuve : Le message portant l’identifiant maximal ne peut jamais être éliminé (aucun processus n’a un identifiant supérieur à ). Il fait donc le tour complet de l’anneau et revient à , qui se déclare élu. Tout autre message est éventuellement éliminé lorsqu’il atteint le processus dont l’identifiant est supérieur à . Donc exactement un processus — — se déclare élu.
6.1.1 Analyse de complexité#
La complexité de Chang-Roberts dépend de la disposition des identifiants sur l’anneau.
Proposition 12 (Complexité de Chang-Roberts).
- Pire cas : messages (identifiants disposés en ordre décroissant).
- Cas moyen : messages (pour une permutation aléatoire des identifiants).
Exemple 6 (Pire cas de Chang-Roberts en Θ(n²)).
Considérons processus disposés en anneau avec les identifiants dans l’ordre décroissant dans le sens de circulation : .
Numérotons les processus dans le sens de circulation, avec . Ainsi a l’identifiant (le maximum), a , etc.
Analysons combien de sauts chaque message effectue avant d’être éliminé :
- : éliminé immédiatement à (1 saut).
- : éliminé à après 2 sauts.
- : éliminé à après sauts.
- : fait le tour complet, sauts.
Total de messages : .
Cette configuration est bien le pire cas : dans toute autre configuration, certains messages sont éliminés plus tôt.
Le pire cas se réalise exactement lorsque les identifiants décroissent dans le sens de circulation. Dans ce cas, chaque message doit « remonter » contre tous les identifiants inférieurs avant d’être arrêté par le maximum. Pour des applications pratiques où est grand, on préférera l’algorithme de Peterson qui garantit dans tous les cas.
6.2 Algorithme de Peterson (anneau bidirectionnel)#
L’algorithme de Peterson, publié en 1982, s’applique à un anneau bidirectionnel et garantit une complexité de messages dans le pire cas. L’idée centrale est une élimination par phases : à chaque phase, au moins la moitié des processus encore candidats sont éliminés, ce qui garantit phases, chacune utilisant messages.
Initialement, tous les processus sont actifs (candidats à l’élection). Au cours de chaque phase, chaque processus actif envoie son identifiant courant à ses deux voisins directs et consulte l’identifiant de son voisin gauche et de son « demi-voisin » gauche (le voisin du voisin). Si l’identifiant du voisin direct est le plus grand des trois, ce voisin « survit » et devient le représentant pour la phase suivante ; sinon il est éliminé.
Théorème 13 (Complexité de Peterson en O(n log n)).
L’algorithme de Peterson nécessite messages dans le pire cas.
Preuve (argument de division par deux) : À chaque phase, considérons les processus actifs. Parmi deux processus actifs consécutifs et son voisin gauche actif , au plus l’un des deux peut « survivre » : survit seulement si son identifiant est strictement supérieur à ceux de ses deux voisins actifs. En particulier, et ne peuvent pas survivre tous les deux simultanément (si survit, c’est que son identifiant est plus grand que celui de , donc ne survit pas, et réciproquement). Ainsi, au moins la moitié des processus actifs sont éliminés à chaque phase.
Avec processus actifs initialement, après phases il reste au plus candidats. Le nombre de phases est donc au plus .
Chaque phase consomme au plus messages (chaque processus actif envoie et reçoit un nombre constant de messages, et les processus passifs relaient). Le total est donc .
Intuition 4 (Intuition de la division par deux).
L’argument clé de Peterson est que la condition de survie () est « strictement locale à deux voisins consécutifs » : deux candidats adjacents ne peuvent pas tous deux remplir cette condition simultanément. Cela garantit que le nombre de survivants est au plus la moitié du nombre de candidats, indépendamment de la configuration des identifiants. En phases, on converge nécessairement vers un unique élu.
Comparer avec Chang-Roberts, où l’absence de mécanisme d’élimination local garantie conduit au pire cas : un seul identifiant (le maximum) « balaie » séquentiellement l’anneau, éliminant tous les autres en les rencontrant.
6.2.1 Comparaison des deux algorithmes#
| Algorithme | Topologie | Pire cas | Cas moyen | Élu |
|---|---|---|---|---|
| Chang-Roberts | Unidirectionnel | id max | ||
| Peterson | Bidirectionnel |