Résumé

  • Fischer, Lynch et Paterson démontrent l’existence d’une exécution admissible sans décision pour tout protocole de consensus déterministe et partiellement correct dans leur modèle asynchrone avec au plus une panne.
  • La bivalence conserve deux décisions possibles. En différant un événement critique et en commutant les pas indépendants, l’ordonnanceur peut rester bivalent tout en livrant finalement les messages et en servant les processus.
  • Synchronie partielle, détecteurs de panne et hasard modifient le contrat. Un délai d’attente peut piloter un système, mais il ne transforme pas le silence en preuve de panne.

Lorsqu’un chef cesse de répondre, l’écran d’exploitation propose volontiers deux états : vivant ou mort. Le réseau, lui, n’offre pas cette netteté. Sans borne de temps, un processus arrêté et un processus très lent produisent la même observation. L’intuition centrale de FLP commence dans cet espace entre absence de réponse et connaissance d’une panne.

L’article de 1985 de Michael J. Fischer, Nancy A. Lynch et Michael S. Paterson ne prétend pourtant pas que les systèmes distribués sont condamnés à l’immobilité. Il montre qu’un protocole déterministe, dans un modèle totalement asynchrone, ne peut garantir une décision pour toute exécution admissible dès qu’une seule panne est permise. Le quantificateur est essentiel : une mauvaise exécution existe ; toutes ne sont pas mauvaises.

Un réseau fiable sans promesse temporelle

Les processus sont déterministes et communiquent par messages. Aucune borne ne limite leur vitesse relative ni le temps de transport. Il n’existe pas d’horloge synchronisée capable de distinguer un retard d’un arrêt. Les messages peuvent arriver tard et dans le désordre, mais ils ne sont pas librement perdus : ceux destinés à un processus non fautif doivent finir par être livrés si ce processus continue à recevoir.

Une exécution admissible contient au plus un processus fautif et assure ces livraisons. Un processus non fautif effectue une infinité de pas. Le résultat est donc plus fort qu’une histoire de paquet disparu. La construction de la preuve peut faire avancer tous les processus et épuiser équitablement les messages en attente, tout en empêchant une décision.

La condition de terminaison retenue est volontairement faible : il suffirait qu’un processus décide dans chaque exécution admissible. Montrer que même cette exigence échoue suffit à exclure les garanties plus ambitieuses.

La bivalence comme réserve de futurs

Une configuration réunit les états internes des processus et le contenu du tampon de messages. Elle est 0-valente si toute continuation décisive mène à 0, 1-valente si elle mène à 1, et bivalente lorsque les deux résultats restent accessibles.

La bivalence n’est pas une hésitation psychologique d’un nœud. Elle décrit l’ensemble des futurs encore compatibles avec l’état global. Les auteurs établissent d’abord qu’il existe une configuration initiale bivalente. Si toutes les configurations initiales étaient univalentes, on pourrait passer d’entrées menant à 0 à des entrées menant à 1 en modifiant un processus à la fois. Deux configurations voisines auraient alors des valences opposées. Si précisément ce processus tombait avant d’agir, les autres ne pourraient les distinguer : contradiction.

Vient ensuite l’événement critique. Prenons la réception d’un message par un processus. Si, après tout chemin qui retarde cette réception, son exécution devait forcément rendre l’état univalent, une frontière séparerait deux valences. Or deux événements concernant des processus différents commutent : les exécuter dans un ordre ou l’autre mène au même état. Ce carré de commutation détruit la différence de valence supposée.

Il reste donc toujours un détour fini qui conserve la bivalence avant de servir l’événement choisi. En parcourant équitablement processus et messages, l’ordonnanceur construit une exécution infinie, admissible et non décisive.

Ce que le théorème ne diagnostique pas

Un service réel peut décider des millions de fois. Ses exécutions ordinaires peuvent être favorables ; surtout, son architecture peut introduire des hypothèses absentes de FLP. Le théorème retire une garantie universelle, pas la possibilité pratique du consensus.

Une élection lente n’est pas davantage une preuve de FLP. Perte de paquets, surcharge, défaut logiciel, changement de membres incorrect ou panne corrélée appellent leurs propres éléments. Dire « c’est FLP » sans établir le modèle et la contrainte de sûreté revient à remplacer l’enquête par une référence prestigieuse.

Changer les hypothèses, honnêtement

Dwork, Lynch et Stockmeyer ont décrit la synchronie partielle : une borne peut exister sans être connue, ou ne devenir valable qu’après un instant de stabilisation inconnu. La progression devient alors possible pendant les périodes où cette hypothèse renforcée tient.

Les détecteurs de panne de Chandra et Toueg ajoutent un service d’information défini par des propriétés de complétude et d’exactitude. Ils n’infèrent pas magiquement une panne du silence ; ils introduisent une garantie supplémentaire. Les protocoles aléatoires, illustrés tôt par Ben-Or, abandonnent pour leur part le déterminisme et formulent une terminaison probabiliste.

Ces familles ne contournent pas une erreur de FLP. Elles exploitent sa cartographie : dès que le modèle change, la promesse peut changer.

Une œuvre collective, une discipline durable

Dans son récit rétrospectif, Nancy Lynch rappelle le travail commun : Fischer et elle ont engagé la recherche en 1982, puis Paterson a rejoint l’effort qui a produit la preuve finale. Préserver ces trois noms évite de transformer une contribution collective en mythe individuel.

La leçon d’ingénierie consiste à publier les hypothèses avec les garanties : fautes tolérées, nature des horloges, propriétés du détecteur, priorité donnée à la sûreté et conditions attendues pour la vivacité. FLP n’interdit pas de construire. Il interdit de présenter une dépendance cachée comme une certitude mathématique.

Sources