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 | id max |
La bidirectionnalité de l’anneau est essentielle pour Peterson : l’algorithme nécessite de consulter deux voisins dans la même phase, ce qui requiert une communication dans les deux sens. Sur un anneau strictement unidirectionnel, le meilleur algorithme connu a une complexité de en moyenne mais dans le pire cas (Chang-Roberts). Sur un graphe général, des algorithmes d’élection existent avec une complexité de où est le nombre d’arêtes.
L’élection de chef est une primitive fondamentale pour de nombreux autres algorithmes distribués. En particulier, la solution centralisée à l’exclusion mutuelle (Chapitre 4) et certains protocoles de consensus (Chapitre 9) supposent l’existence d’un coordinateur préalablement élu. Dans des systèmes dynamiques où les processus peuvent tomber en panne et redémarrer, l’élection doit être périodiquement relancée — c’est le rôle des détecteurs de pannes et des protocoles de ré-élection.
7 Détection de terminaison#
Dans un système distribué, la notion même de « fin du calcul » est beaucoup plus subtile que dans un programme séquentiel. Lorsqu’un processus unique termine sa boucle principale, on sait immédiatement que le calcul est achevé. Dans un système distribué, en revanche, plusieurs processus s’exécutent en parallèle et se transmettent des messages : un processus peut devenir inactif, puis être réveillé par un message qu’un autre processus lui avait envoyé avant même de s’endormir. De l’extérieur, il est impossible de distinguer ce cas d’une terminaison effective.
Ce chapitre étudie le problème de la détection de terminaison : comment un observateur extérieur — ou l’un des processus lui-même — peut-il déterminer de manière sûre que le calcul distribué a globalement terminé, sans interrompre le calcul ni disposer d’une horloge globale ? Nous présenterons trois approches classiques : le jeton de Dijkstra–Safra pour les anneaux synchrones, l’algorithme de Safra avec compteurs pour les systèmes asynchrones, et le schéma de crédit de Mattern pour les calculs diffusants.
7.1 Le problème de la terminaison#
Considérons un ensemble de processus qui participent à un calcul distribué. À tout instant, chaque processus est soit actif (il calcule ou vient d’envoyer un message), soit inactif (il n’effectue aucun calcul local). Un processus inactif peut redevenir actif à tout moment s’il reçoit un message.
L’approche naïve consiste à vérifier périodiquement si tous les processus sont inactifs. Cette vérification est cependant insuffisante, et ce pour une raison fondamentale : un message peut être en transit dans le réseau. Si a envoyé un message à avant de s’endormir, et si est également inactif au moment de la vérification, alors l’observateur peut conclure à tort que le calcul est terminé. Mais dès que recevra le message, il se réveillera et continuera le calcul.
Définition 14 (Terminaison globale).
Un calcul distribué est dit globalement terminé si et seulement si les deux conditions suivantes sont simultanément satisfaites :
-
Tous les processus sont inactifs : pour tout , le processus n’effectue aucune action locale.
-
Aucun message n’est en transit : pour tout couple , il n’existe aucun message envoyé par à qui n’ait pas encore été reçu par .
Cette définition met en lumière la difficulté fondamentale : les messages en transit sont invisibles à un observateur externe. Un gestionnaire qui ne surveille que les états des processus ne peut pas savoir combien de messages circulent encore dans le réseau.
Exemple 7 (Échec de la détection naïve).
Supposons deux processus et . est actif, envoie un message à à l’instant , puis devient inactif à . , de son côté, termine ses propres calculs et devient inactif à .
Un gestionnaire qui vérifie les états à constate : inactif, inactif. Il déclare la terminaison. C’est une erreur : le message n’a pas encore été délivré. À , reçoit , se réactive, et reprend le calcul.
La difficulté fondamentale est que l’état global visible (les états des processus) et l’état global réel (incluant les messages en transit) divergent. Toute solution au problème doit donc, d’une façon ou d’une autre, comptabiliser les messages en vol. Les trois algorithmes que nous allons étudier utilisent des mécanismes différents pour réaliser ce comptage : un jeton coloré, des compteurs par processus, ou une fraction de « crédit ».
7.2 Jeton de Dijkstra–Safra#
La première solution que nous présentons est applicable dans un modèle synchrone où les processus sont organisés en anneau : , chaque processus n’ayant pour voisin de droite que le processus suivant. Le processus joue le rôle d’initiateur : c’est lui qui déclenche la détection et interprète le résultat.
L’idée centrale est de faire circuler un jeton sur l’anneau. Lorsque le jeton revient à après un tour complet, peut tenter de conclure à la terminaison. Pour détecter les messages envoyés « à rebours » dans l’anneau (c’est-à-dire d’un processus vers un processus avec , ce qui pourrait réactiver un processus déjà visité par le jeton), on utilise une couleur associée au jeton.
Chaque processus est coloré blanc (inactif, n’a envoyé aucun message depuis qu’il a tenu le jeton) ou rouge (actif, ou a envoyé un message à un processus en amont dans l’anneau depuis la dernière fois qu’il a tenu le jeton). Le jeton lui-même est blanc ou noir.
Théorème 14 (Correction du jeton de Dijkstra–Safra).
L’algorithme du jeton de Dijkstra–Safra est correct : si détecte la terminaison (jeton blanc revenant à avec inactif pendant tout le tour), alors le calcul est effectivement globalement terminé.
Réciproquement, si le calcul termine, détectera la terminaison en un nombre fini de tours.
Preuve 2.
Sûreté (pas de fausse détection). Supposons que reçoive un jeton blanc alors qu’il était inactif pendant tout le tour. Un jeton blanc signifie qu’aucun processus visité n’a envoyé de message à un processus avec (sinon le jeton serait noir). Tous les processus ayant passé le jeton étaient inactifs au moment du passage. Aucun message envoyé à rebours n’a pu réactiver un processus déjà visité. Donc, au moment où conclut, tous les processus sont bien inactifs et aucun message vers un processus antérieur n’est en transit.
Vivacité (détection éventuelle). Si le calcul termine à un instant , alors à partir de tous les processus restent inactifs et n’envoient plus de messages. Le prochain tour de jeton initié après sera entièrement blanc, et détectera la terminaison.
Le mécanisme de contamination par la couleur noire est la clef de la correction. Un processus qui envoie un message à avec après que le jeton ait déjà visité pourrait faire croire à tort que est définitivement inactif. En noircissant le jeton, force à lancer un nouveau tour, permettant ainsi à d’être observé à nouveau après réception du message.
7.3 Algorithme de Safra (asynchrone)#
Le jeton de Dijkstra–Safra suppose un modèle synchrone et une topologie en anneau. Dans un système asynchrone de topologie quelconque, on ne peut pas garantir que les messages sont délivrés dans un ordre connu. Safra a proposé une généralisation qui remédie à ces limitations en associant à chaque processus un compteur de messages qui trace explicitement le nombre de messages envoyés et reçus.
L’idée est la suivante : si la somme de tous les compteurs vaut zéro, alors le nombre de messages envoyés est exactement égal au nombre de messages reçus — autrement dit, tous les messages en transit ont été délivrés. Couplée à la condition « tous les processus inactifs », cette observation suffit à garantir la terminaison globale.
Théorème 15 (Correction de Safra).
L’algorithme de Safra est correct. La condition est équivalente à « aucun message n’est en transit » si tous les processus ont contribué leur compteur au jeton pendant le même tour.
Formellement : la terminaison est détectée si et seulement si le calcul est globalement terminé.
Preuve 3.
Chaque envoi incrémente un de , et chaque réception décrémente un de . Si tout message envoyé a été reçu, alors pour chaque message envoyé par et reçu par , la contribution à et à se compensent. La somme globale est donc nulle si et seulement si le nombre de messages reçus est égal au nombre de messages envoyés, c’est-à-dire si aucun message n’est en transit.
La condition de couleur blanche du jeton garantit qu’aucun processus n’a été réactivé après avoir transmis le jeton, de sorte que les compteurs collectés reflètent bien l’état au moment de la collecte.
L’avantage majeur de l’algorithme de Safra sur le jeton de Dijkstra est qu’il fonctionne dans un modèle asynchrone : les processus n’ont pas besoin de se synchroniser sur un cycle d’horloge commun. Les messages peuvent être retardés arbitrairement. Cela rend l’algorithme applicable à une classe beaucoup plus large de systèmes distribués réels. En contrepartie, la preuve de correction est plus délicate car les compteurs sont collectés à des instants différents.
7.4 Schéma de crédit de Mattern#
L’algorithme de Mattern adopte une approche radicalement différente, inspirée de la comptabilité financière : chaque processus et chaque message dispose d’une fraction de crédit, et la terminaison est détectée quand l’initiateur a récupéré la totalité du crédit distribué dans le système.
Ce schéma est particulièrement adapté aux calculs diffusants (diffusing computations), c’est-à-dire les calculs qui démarrent à partir d’un seul processus initiateur et se propagent en créant dynamiquement des « sous-tâches » qui peuvent elles-mêmes en créer d’autres. L’arbre de calcul n’est pas connu à l’avance, ce qui rend inapplicables les approches basées sur une topologie fixe.
Le schéma de crédit est une astuce comptable élégante : chaque fraction de crédit représente une « dette » d’un processus ou d’un message envers l’initiateur. Aussi longtemps qu’un message est en transit ou qu’un processus est actif, une fraction du crédit est « immobilisée ». Quand le crédit total revient à , cela signifie que toutes les dettes ont été remboursées — tous les processus ont terminé et tous les messages ont été reçus. La division par deux assure que le crédit total dans le système est toujours conservé (il se redistribue sans être créé ni détruit) et peut être arbitrairement petit pour les calculs très ramifiés, ce qui peut poser des problèmes de précision en virgule flottante. En pratique, on représente le crédit en notation exacte (fractions ou entiers binaires).
Les trois algorithmes présentés dans ce chapitre résolvent le même problème fondamental avec des compromis différents. Le jeton de Dijkstra–Safra est simple et efficace pour les anneaux synchrones. L’algorithme de Safra généralise au cas asynchrone au prix d’une légère complexité supplémentaire. Le schéma de crédit de Mattern est le plus général : il s’applique à n’importe quel calcul diffusant, sans supposer une topologie fixe ni un modèle synchrone. Le choix entre ces approches dépend des hypothèses du modèle et de la structure du calcul distribué considéré.
8 Instantanés globaux#
Un système distribué en cours d’exécution est, par nature, un objet difficile à observer. Chaque processus possède un état local qui évolue continuellement, et les canaux de communication transportent des messages dont ni l’expéditeur ni le destinataire ne connaît exactement la position dans le réseau à un instant donné. Pourtant, de nombreuses tâches essentielles — la vérification d’invariants globaux, la détection de blocages (deadlocks), la reprise sur erreur (checkpointing), ou encore le débogage — nécessitent de prendre une « photographie » cohérente de l’état global du système à un instant donné.
Le problème de l’instantané global (global snapshot) consiste précisément à capturer cet état de manière cohérente, c’est-à-dire de façon à ce que la photo résultante corresponde à un état que le système aurait pu effectivement traverser dans une exécution séquentielle. La difficulté fondamentale est qu’il est impossible d’arrêter le système pour le photographier : les processus continuent d’envoyer et de recevoir des messages pendant la procédure de capture. Il faut donc concevoir un protocole distribué qui coordonne la prise de photo sans perturber le calcul en cours.
Ce chapitre développe les notions de coupe cohérente et d’état global cohérent, puis présente deux algorithmes classiques : Chandy–Lamport pour les canaux FIFO, et Lai–Yang pour les canaux non-FIFO.
8.1 État global et coupe cohérente#
Pour formaliser ce que signifie un « état global cohérent », nous devons d’abord introduire le vocabulaire des historiques de processus et des coupes.
Définition 15 (Historique d'un processus).
L’historique du processus , noté , est la séquence (totalement ordonnée) de tous les événements que a exécutés :
où désigne le -ième événement de . Un événement est soit une action locale, soit un envoi de message, soit une réception de message.
Définition 16 (Coupe).
Une coupe d’un système à processus est un tuple où représente le nombre d’événements de inclus dans la coupe. La coupe sélectionne le préfixe de chaque historique local .
L’état global associé à la coupe est la collection des états locaux où est l’état de après son -ième événement.
Une coupe sépare le passé du futur pour chaque processus, mais elle ne garantit pas en elle-même la cohérence. Un problème se pose quand un message semble avoir été reçu avant d’avoir été envoyé : cela signifie que l’envoi se situe après la coupe sur le processus émetteur, mais la réception se situe avant la coupe sur le processus récepteur. Un tel état global ne peut jamais avoir existé dans une exécution réelle.
Définition 17 (Coupe cohérente).
Une coupe est dite cohérente si et seulement si : pour tout couple d’événements et ,
Autrement dit, si un événement est inclus dans la coupe et qu’un événement précède causalement , alors est également inclus dans la coupe.
Cette condition peut s’énoncer de manière équivalente en termes de messages : une coupe est cohérente si et seulement si aucun message envoyé après la coupe n’est reçu avant la coupe. Cette formulation est plus opératoire pour concevoir des algorithmes.
Une coupe est cohérente si et seulement si : pour tout canal de vers , le nombre de messages envoyés sur et inclus dans (c’est-à-dire envoyés lors des premiers événements de ) est supérieur ou égal au nombre de messages reçus sur et inclus dans (c’est-à-dire reçus lors des premiers événements de ).
Preuve 4.
() Supposons la coupe cohérente. Soit un message reçu par lors de son -ième événement, avec (réception dans la coupe). Alors la réception est dans . L’envoi précède causalement la réception (règle de communication de ). Par cohérence, , donc l’envoi a lieu parmi les premiers événements de . Tout message reçu dans la coupe a donc été envoyé dans la coupe.
() Réciproquement, si tout message reçu dans a été envoyé dans , alors il n’y a aucun message envoyé après la coupe et reçu avant, ce qui est précisément la définition d’une coupe cohérente.
L’état du canal dans une coupe cohérente est l’ensemble des messages envoyés sur dans la coupe mais pas encore reçus dans la coupe : ce sont les messages qui étaient en transit au moment de l’instantané.
Exemple 8 (Coupe cohérente et incohérente).
Considérons trois processus , , avec les événements suivants : envoie à lors de son événement ; reçoit lors de son événement.
-
Coupe cohérente : — l’envoi de (événement 3 de ) est inclus, et la réception de (événement 2 de ) l’est aussi. Cohérente.
-
Coupe cohérente avec message en transit : — l’envoi de est inclus, mais la réception ne l’est pas (). L’état du canal contient . C’est toujours cohérent : il n’y a pas de message reçu avant d’avoir été envoyé.
-
Coupe incohérente : — la réception de (événement 2 de ) est incluse, mais l’envoi (événement 3 de ) ne l’est pas (). Cela correspond à un état global impossible.
8.2 Algorithme de Chandy–Lamport (canaux FIFO)#
L’algorithme de Chandy et Lamport (1985) est la première solution pratique au problème de l’instantané global. Il suppose que les canaux de communication sont FIFO : les messages émis sur un canal sont reçus dans l’ordre dans lequel ils ont été envoyés. Cette hypothèse est satisfaite par la grande majorité des protocoles de transport (TCP, par exemple).
L’idée directrice est d’utiliser des messages spéciaux appelés marqueurs pour délimiter la frontière de la coupe sur chaque canal. Un marqueur envoyé par sur le canal signifie : « J’ai enregistré mon état ; tous les messages que j’ai envoyés sur ce canal avant ce marqueur font partie de l’instantané ; ceux envoyés après n’en font pas partie. » Grâce à la propriété FIFO, sait exactement quels messages de précèdent la coupe (ceux arrivés avant le marqueur) et lesquels la suivent.
L’état global enregistré par l’algorithme de Chandy–Lamport est une coupe cohérente : il correspond à un état global que le système a pu effectivement traverser dans une exécution correcte.
Preuve 5.
Il suffit de montrer que l’état enregistré ne contient aucun message reçu avant son envoi. Soit un message envoyé par à . Deux cas se présentent :
- est envoyé avant que n’enregistre son état. Alors est envoyé avant le marqueur de sur . Par FIFO, arrive avant le marqueur chez . Soit enregistre son état à la réception du marqueur : est arrivé avant, donc il est dans l’état du canal si avait déjà enregistré son état, ou il est inclus implicitement dans l’état local de sinon. Dans les deux cas, la réception de est dans la coupe.
- est envoyé après que a enregistré son état. Alors est envoyé après le marqueur de . Par FIFO, arrive après le marqueur chez , donc après que a enregistré son propre état. La réception de n’est pas dans la coupe.
Dans les deux cas, il n’y a pas de message reçu dans la coupe mais envoyé hors de la coupe. La coupe est donc cohérente.
L’hypothèse FIFO est indispensable à la correction. Si les messages pouvaient se dépasser sur un canal, un message envoyé après le marqueur pourrait arriver avant lui chez . enregistrerait alors dans l’état du canal, alors que est postérieur à la coupe sur — produisant une coupe incohérente.
Exemple 9 (Trace de l'algorithme de Chandy–Lamport).
Considérons trois processus , , dans un réseau quelconque.
-
décide d’initier le snapshot. Il enregistre son état local , puis envoie un MARQUEUR sur et sur .
-
Avant l’arrivée du MARQUEUR, reçoit un message applicatif de .
-
reçoit le MARQUEUR de . Comme n’a pas encore enregistré son état, il enregistre maintenant. L’état du canal est vide (le MARQUEUR est le premier message post-coupe). envoie un MARQUEUR sur .
-
reçoit le MARQUEUR de en premier. Il enregistre et commence à enregistrer les messages reçus sur .
-
reçoit le message de (envoyé avant le MARQUEUR de ). Ce message est ajouté à l’état du canal .
-
reçoit le MARQUEUR de . L’état du canal est .
L’instantané global est avec état de canal , , .
8.3 Lai–Yang (canaux non-FIFO)#
Lorsque les canaux de communication ne sont pas FIFO, l’approche de Chandy–Lamport échoue : un message envoyé après le marqueur pourrait arriver avant lui chez le destinataire, brouillant la frontière de la coupe. L’algorithme de Lai et Yang (1987) contourne ce problème en supprimant entièrement les marqueurs explicites, au profit d’un mécanisme de coloration et de piggybacking (ajout d’informations aux messages applicatifs).
L’intuition est simple : avant le snapshot, les processus sont blancs ; après avoir décidé de participer au snapshot, ils deviennent rouges. Tout message envoyé par un processus rouge est lui-même marqué rouge. Lorsqu’un processus blanc reçoit un message rouge, il sait que l’expéditeur a déjà pris son snapshot : il doit donc prendre le sien avant de traiter ce message (pour que sa coupe soit cohérente avec celle de l’expéditeur).
L’état global enregistré par l’algorithme de Lai–Yang est une coupe cohérente, même dans les systèmes à canaux non-FIFO.
Preuve 6.
Soit un message envoyé par à . Quatre cas selon les couleurs à l’envoi et à la réception :
-
blanc, blanc lors de la réception. est envoyé et reçu avant les snapshots respectifs. L’envoi et la réception sont tous deux dans la coupe (ou tous deux hors de la coupe si les snapshots ont lieu après). Cohérent.
-
blanc, rouge lors de la réception. a été envoyé avant le snapshot de , mais reçu après le snapshot de . ajoute à l’état du canal : la coupe reconnaît que était en transit. Cohérent.
-
rouge, blanc lors de la réception. reçoit un message rouge alors qu’il est encore blanc : il doit d’abord enregistrer son état avant de traiter . Donc le snapshot de est antérieur à la réception de . est donc reçu après la coupe de . Or rouge est envoyé après la coupe de . Pas de problème.
-
rouge, rouge lors de la réception. Les deux snapshots sont antérieurs à l’envoi et à la réception de . est hors coupe. Cohérent.
Dans tous les cas, aucun message n’est reçu dans la coupe sans avoir été envoyé dans la coupe. La coupe est cohérente.
L’algorithme de Lai–Yang évite d’envoyer des messages MARQUEUR supplémentaires sur chaque canal (ce qui nécessiterait messages supplémentaires pour un graphe complet). En attachant les informations de couleur aux messages applicatifs (piggybacking), le surcoût en messages est nul : seul un bit de couleur est ajouté à chaque message. En revanche, l’algorithme requiert que chaque processus conserve en mémoire les messages blancs reçus après son passage au rouge, jusqu’à ce que tous les expéditeurs potentiels soient devenus rouges.
La couleur dans Lai–Yang joue le même rôle conceptuel que le marqueur dans Chandy–Lamport : elle délimite la frontière de la coupe sur chaque canal. La différence est que dans Chandy–Lamport, le marqueur est un message explicite qui se déplace dans le canal, tirant parti de l’ordre FIFO ; dans Lai–Yang, la couleur est une information implicite attachée à chaque message, ce qui permet de fonctionner sans hypothèse d’ordre sur les canaux.
Les deux algorithmes présentés dans ce chapitre illustrent un principe général important en algorithmique distribuée : la même spécification (coupe cohérente) peut être réalisée par des mécanismes très différents, chacun adapté aux hypothèses du modèle sous-jacent. Dans les systèmes réels, le choix entre ces deux algorithmes — ou leurs nombreuses variantes — dépend des garanties offertes par la couche réseau et du budget en messages supplémentaires que l’application peut se permettre.
9 Consensus et tolérance byzantine#
Le consensus est le problème le plus fondamental de l’algorithmique distribuée tolérante aux fautes. Son énoncé est d’une simplicité trompeuse : plusieurs processus démarrent chacun avec une valeur initiale, et ils doivent tous se mettre d’accord sur une même valeur finale. Cette tâche banale dans un système centralisé devient extraordinairement difficile dès que certains composants peuvent tomber en panne — qu’il s’agisse d’arrêts simples (crash failures) ou de comportements malveillants (Byzantine failures).
Les résultats présentés dans ce chapitre forment le cœur théorique des systèmes distribués tolérants aux fautes. Nous verrons d’abord la définition formelle du consensus et ses exigences précises, puis le célèbre problème des généraux byzantins, avant d’établir l’impossibilité fondamentale de Fischer, Lynch et Paterson (FLP) dans les systèmes asynchrones. Nous terminerons par l’algorithme Flood-Set, qui montre que le consensus est soluble dans les systèmes synchrones.
9.1 Le problème du consensus#
Formellement, le problème du consensus implique processus , chacun possédant une valeur initiale (ou plus généralement dans un domaine ). Les processus communiquent par échange de messages, et l’objectif est que chaque processus finisse par décider (decide) une valeur, de sorte que toutes les décisions soient identiques et reflètent les entrées initiales.
Définition 18 (Problème du consensus).
Un algorithme de consensus doit satisfaire les trois propriétés suivantes pour tous les processus corrects (non défaillants) :
-
Accord (Agreement). Deux processus corrects quelconques décident la même valeur : si décide et décide , alors .
-
Validité (Validity). La valeur décidée est la valeur initiale de l’un des processus corrects. En particulier, si tous les processus corrects ont la même valeur initiale , ils doivent décider .
-
Terminaison (Termination). Tout processus correct décide en un temps fini.
Ces trois propriétés semblent raisonnables, voire minimales. La propriété d’accord garantit l’utilité du consensus : tous les processus coordonnés aboutissent au même résultat. La propriété de validité empêche les solutions triviales — un algorithme qui décide toujours satisferait l’accord, mais violerait la validité si les entrées sont toutes égales à . La terminaison assure que l’algorithme progresse effectivement.
La difficulté fondamentale vient de la combinaison de ces trois propriétés face aux pannes. En leur absence, le consensus est trivial : chaque processus diffuse sa valeur, collecte toutes les valeurs, et prend le minimum. En présence de pannes, certains processus peuvent ne jamais répondre. Comment distinguer un processus lent d’un processus tombé ? Dans un système asynchrone, cette distinction est impossible — c’est précisément ce qu’exploite le résultat d’impossibilité FLP.
9.2 Problème des généraux byzantins#
Le modèle de panne le plus général — et le plus dangereux — est la faute byzantine. Un processus byzantin peut se comporter de manière arbitraire : il peut envoyer des messages contradictoires à des processus différents, envoyer des messages contenant des valeurs erronées, ou ne rien envoyer du tout. Ce modèle a été introduit par Lamport, Shostak et Pease (1982) sous la métaphore militaire des généraux byzantins : des généraux d’une armée doivent se coordonner pour attaquer ou se retirer, mais certains d’entre eux sont des traîtres qui cherchent à empêcher l’accord.
Un processus est dit byzantin (ou défaillant de manière arbitraire) s’il peut s’écarter arbitrairement de son comportement spécifié. Un processus byzantin peut : envoyer des messages avec des contenus erronés, envoyer des messages différents à des destinataires différents pour le même événement, retarder ou omettre des messages, ou encore se coordonner avec d’autres processus byzantins pour compromettre le système.
Le résultat central sur le consensus byzantin est une condition nécessaire et suffisante sur le nombre de processus.
Théorème 19 (Condition nécessaire et suffisante — Lamport-Shostak-Pease (1982)).
Dans un système de processus dont au plus sont byzantins, le consensus byzantin est soluble si et seulement si
La preuve de ce théorème comporte deux parties : la borne inférieure (impossibilité pour ) et la borne supérieure (existence d’un protocole pour ).
Borne inférieure : impossibilité pour .
Supposons processus divisés en trois groupes , , de taille chacun. Supposons que le groupe est byzantin. Voici le nœud de l’argument : du point de vue des processus de , le groupe byzantin peut se faire passer pour un groupe honnête ayant une valeur différente de celle que présente à . Plus précisément :
- envoie « » aux processus de et .
- envoie « » aux processus de (dans une variante à 4 processus).
Les processus de et ne peuvent pas distinguer ce scénario d’un scénario où est honnête et a réellement la valeur que leur a communiquée. Avec seulement processus dans chaque groupe, il est impossible de former une majorité fiable pour démasquer les traîtres. On peut construire formellement une contradiction : si un algorithme tolère fautes byzantines avec , on peut trouver deux exécutions indiscernables par certains processus mais où ces processus doivent décider des valeurs différentes pour satisfaire validité et accord — une contradiction.
Borne supérieure : protocole avec tours pour .
Pour , il existe des protocoles qui atteignent le consensus byzantin. L’idée générale est de faire tourner rounds d’échange d’informations : dans chaque round, chaque processus diffuse toutes les valeurs qu’il a collectées jusqu’alors. Après rounds, les processus corrects ont suffisamment de redondance pour distinguer les informations cohérentes (venant de processus corrects) des informations incohérentes (venant de processus byzantins), et peuvent appliquer un vote majoritaire.
Exemple 10 (Cas n=4, f=1).
Considérons processus : , , (honnêtes, avec ) et (byzantin). envoie « 1 » à et , mais envoie « 0 » à .
Round 1 — vote naïf. Chaque processus diffuse sa valeur initiale, puis effectue un vote majoritaire sur les valeurs reçues.
-
reçoit : {
:1,
:1,
:1,
:1} → vote majorité → décide 1.
-
reçoit : {
:1,
:1,
:1,
:1} → vote majorité → décide 1.
-
reçoit : {
:1,
:1,
:0,
:1} → vote majorité → décide 1.
Ici l’accord est atteint par chance : n’a pas semé assez de discorde. Mais si coordonne ses mensonges différemment (envoie « 1 » à , « 0 » à et ), alors et peuvent aboutir à des décisions différentes. Un seul tour est insuffisant en général pour . Il faut tours pour garantir l’accord.
9.3 Impossibilité FLP#
Le résultat de Fischer, Lynch et Paterson (1985) est l’un des théorèmes les plus importants — et les plus surprenants — de l’informatique distribuée. Il établit qu’il est impossible de résoudre le consensus dans un système asynchrone, même si les seules pannes possibles sont des crashs (arrêts définitifs) et qu’une seule panne peut survenir.
Ce résultat peut sembler paradoxal : un seul processus peut tomber, les autres fonctionnent parfaitement, et pourtant aucun algorithme déterministe ne peut garantir la terminaison. La clé est l’asynchronisme : dans un système asynchrone, il n’existe aucune borne sur les délais de transmission des messages. Un processus qui ne répond pas est-il tombé en panne ou simplement lent ? Il est impossible de le savoir.
Dans un système distribué asynchrone, il n’existe aucun algorithme déterministe qui résout le consensus même avec au plus une panne de type crash.
La preuve formelle repose sur la notion de configuration bivalente : une configuration est bivalente si les deux valeurs de décision ( et ) sont encore possibles à partir de cet état, selon la suite des événements futurs. Une configuration est univalente si une seule valeur de décision est encore accessible.
Esquisse de preuve.
On montre deux lemmes :
-
Existence d’une configuration initiale bivalente. Si une configuration initiale était univalente pour toutes les valeurs des processus, il suffirait de modifier la valeur d’un processus (possiblement en panne) pour passer d’une configuration 0-valente à une configuration 1-valente. On montre qu’il doit exister une configuration initiale bivalente en considérant des chemins entre configurations 0-valentes et 1-valentes.
-
Depuis toute configuration bivalente, il existe un événement qui maintient la bivalence. Un algorithme qui tente de décider doit passer d’une configuration bivalente à une configuration univalente. Mais quel que soit le prochain événement exécuté (réception d’un message), on peut construire un ordonnancement des événements qui maintient la bivalence, en retardant indéfiniment le message déterminant. L’asynchronisme permet précisément ce report : il est toujours possible de prétendre qu’un message est simplement retardé plutôt que perdu.
La combinaison de ces deux lemmes montre qu’un algorithme déterministe ne peut jamais forcer la terminaison : il y aura toujours des exécutions où l’algorithme est maintenu indéfiniment dans une configuration bivalente.
Remarque 25.
Le théorème FLP explique pourquoi tous les algorithmes de consensus pratiques — Paxos de Lamport, Raft de Ongaro et Ousterhout, Zab de Zookeeper — reposent sur des hypothèses supplémentaires qui sortent du cadre purement asynchrone :
- Synchronie partielle (partial synchrony) : il existe une borne sur les délais, mais elle n’est pas connue à l’avance.
- Aléatoire : certains algorithmes utilisent des bits aléatoires pour briser la symétrie et échapper aux configurations bivalentes.
Dans ces modèles étendus, le consensus est soluble, mais FLP rappelle que cette solvabilité repose toujours sur des hypothèses non triviales concernant le modèle.
L’impossibilité FLP n’est pas un problème de complexité (« le problème est trop dur à calculer ») mais un problème de calculabilité dans un modèle spécifique. Il ne s’agit pas de trouver un algorithme plus efficace : aucun algorithme déterministe ne peut résoudre le consensus dans le modèle asynchrone avec crashs, quelle que soit sa complexité en temps ou en messages. C’est une limite fondamentale du modèle lui-même, comparable à l’indécidabilité du problème de l’arrêt pour les machines de Turing.
9.4 Algorithme Flood-Set (synchrone,  phases)#
Le résultat FLP ferme la porte au consensus asynchrone, mais ouvre la voie à une question naturelle : le consensus est-il soluble dans un modèle synchrone ? La réponse est oui — et l’algorithme Flood-Set en donne une construction simple et élégante.
Dans le modèle synchrone, les processus s’exécutent en rondes : à chaque ronde, chaque processus envoie des messages, puis reçoit tous les messages envoyés pendant cette ronde (sauf ceux des processus crashés). Le système garantit une borne connue sur les délais. Les processus peuvent crasher (arrêt définitif), mais au plus d’entre eux.
L’idée centrale du Flood-Set est d’inonder le réseau avec toutes les valeurs initiales connues. Après suffisamment de rondes, tous les processus vivants ont la même vue de l’ensemble des valeurs initiales et peuvent donc appliquer la même fonction déterministe pour décider.
Après rondes, tous les processus corrects ont le même ensemble . En conséquence, ils décident tous la même valeur.
Preuve 7.
Nous montrons que si un processus correct ajoute une valeur à son ensemble lors de la ronde , alors tout autre processus correct aura dans son ensemble à la fin de la ronde (sauf si crashe dans la ronde ).
Il y a au plus crashs. Par le principe des tiroirs, sur rondes, il existe au moins une ronde sans aucun crash. Pendant la ronde , tous les processus corrects reçoivent le message de tous les autres processus corrects. Donc à la fin de la ronde , tous ont le même ensemble (l’union de tous les ensembles avant la ronde ).
Plus précisément : si une valeur est dans avant la ronde , alors la diffuse pendant et tous les processus corrects la reçoivent. Si est introduite pendant par un processus qui ne crashe pas (puisque est sans crash), tous les processus la reçoivent. Donc après , tous les processus corrects ont le même ensemble, et ils décident tous .
L’algorithme Flood-Set effectue exactement rondes. À chaque ronde, chaque processus envoie son ensemble à tous les processus, soit messages par processus et messages par ronde. La taille de chaque message est où (l’ensemble contient au plus valeurs distinctes). La complexité totale en messages est donc valeurs transmises, sur rondes.
Le nombre de rondes est optimal. Avec rondes seulement, il serait possible que processus crashent, un par ronde, chacun au moment précis où il vient d’envoyer son ensemble à certains processus mais pas à d’autres. Cela peut créer une asymétrie d’information entre les processus survivants, empêchant l’accord. Avec rondes, on garantit qu’il y a au moins une ronde « propre » (sans crash) après laquelle toute l’information est uniformément distribuée.
En résumé, ce chapitre a établi les résultats fondamentaux du consensus distribué : la condition pour le consensus byzantin, l’impossibilité FLP dans le modèle asynchrone avec crashs, et la constructivité du Flood-Set dans le modèle synchrone. Ces résultats délimitent précisément ce qui est possible et ce qui ne l’est pas en matière de tolérance aux fautes, et constituent la base théorique indispensable à la conception des systèmes distribués robustes modernes.