Travaux pratiques · ESILV · 2024
Consensus de Ben-Or
Des machines doivent se mettre d'accord sur une valeur, 0 ou 1. Certaines peuvent tomber en panne sans prévenir, les messages arrivent dans le désordre, et aucune horloge commune ne dit quand arrêter d'attendre. En cours de technologies décentralisées, j'ai implémenté l'algorithme de Ben-Or en TypeScript, un petit serveur web par machine. Ici, le même algorithme tourne dans votre navigateur, et c'est vous qui choisissez les pannes.
Portage web réalisé avec une assistance d'IA, à partir de mon code du TP.
Lancer un consensus
Chaque cercle est un nœud, et sa couleur la valeur qu'il défend. Les points qui circulent sont les messages : pleins pour une proposition, creux pour un vote. Un nœud entouré a décidé.
Scénarios des tests du TP
Et si…
- 0tour atteint
- 0messages envoyés
- 0pile ou face
- 0nœuds décidés
Ce qui se passe
Les derniers raisonnements des nœuds, du plus récent au plus ancien.
Mille exécutions
Même réseau, mêmes pannes : seuls changent l'ordre d'arrivée des messages et les pièces.
Nombre d'exécutions selon le tour auquel le dernier nœud en vie a décidé
Voir le tableau
| Tour de décision | Exécutions |
|---|
Un tour, deux phases
Tous les nœuds en vie exécutent la même boucle. Aucun ne sait qui est en panne : il avance dès qu'il a entendu assez de monde.
1. Proposer
diffuser (proposition, k, x)
attendre N − F propositions du tour k
si plus de N/2 disent v : voter v
sinon : voter ?Plus de la moitié de tous les nœuds, pas seulement de ceux entendus : deux nœuds ne peuvent donc jamais voter pour deux valeurs différentes au même tour.
2. Voter
diffuser (vote, k, v)
attendre N − F votes du tour k
si F + 1 votes pour v : décider v
si un vote pour v : x ← v
sinon : x ← pile ou face
passer au tour k + 1Avec F + 1 votes pour v, même un nœud qui en rate F en voit au moins un : tous repartent avec v, et le tour suivant est unanime.
Pourquoi tirer à pile ou face ?
Fischer, Lynch et Paterson ont démontré en 1983 qu'aucun algorithme déterministe ne garantit le consensus dans un réseau asynchrone où ne serait-ce qu'une machine peut tomber en panne. Une machine lente ne se distingue pas d'une machine morte, et un ordre d'arrivée des messages assez défavorable fait hésiter le réseau indéfiniment.
La même année, Michael Ben-Or contourne l'obstacle : quand aucun vote ne départage, chaque nœud tire à pile ou face. Tôt ou tard, assez de pièces tombent du même côté. L'accord n'est jamais violé ; seule la durée devient aléatoire, et la probabilité de ne jamais conclure est nulle.
Le revers apparaît dans les mille exécutions à 12 nœuds divisés : avec une pièce par nœud, il faut parfois des dizaines de tours pour que la chance s'aligne. Les protocoles plus récents partagent une « pièce commune » pour conclure en quelques tours.
Combien de pannes ?
Attendre N − F, jamais N
Personne ne sait qui est en panne. Attendre la réponse de tous, c'est risquer d'attendre un mort : on attend donc N − F messages, et l'on avance avec ceux-là.
Moins de N/2
Si F atteint N/2, un nœud n'entend que N/2 propositions au plus : jamais de majorité, donc jamais de décision. L'algorithme ne se trompe pas, il ne conclut plus. C'est le scénario « Au-delà du seuil », repris d'un test du TP.
Pas plus que prévu
Si plus de F nœuds tombent, les survivants attendent des messages qui ne viendront jamais : le réseau se bloque. Essayez « Plus de pannes que prévu », ou mettez des nœuds en panne pendant une exécution.
Ici, un nœud en panne se tait : c'est une panne « franche ». Un nœud malveillant, lui, pourrait mentir. La variante byzantine de Ben-Or suppose alors moins d'un cinquième de nœuds malveillants, et les protocoles de type PBFT moins d'un tiers.
Du TP au navigateur
Le TP
- TypeScript et Express : chaque nœud est un serveur HTTP, sur le port 3000 + son numéro
- Routes /start, /stop, /message, /status et /getState
- Énoncé et tests fournis, implémentation personnelle : les 9 tests visibles passent, relancés en 2026
Le même algorithme
- Mêmes seuils : N − F messages, majorité stricte de N/2, décision à F + 1 votes
- Mêmes messages : proposition et vote, avec leur numéro de tour
- Mêmes scénarios que les tests, réseau et valeurs compris
Ce que la page change
- Un réseau simulé : délais aléatoires, messages dans le désordre, pannes en cours de route
- Un nœud qui a décidé continue de participer. Dans mon TP, il se taisait : sans effet dans les tests, où tous les nœuds en vie reçoivent les mêmes messages et décident ensemble, mais de quoi bloquer les retardataires quand les décisions tombent à des tours différents
Ce que j'en ai retenu
- Penser asynchrone Sans horloge commune ni ordre garanti, un algorithme distribué ne peut s'appuyer que sur des seuils de messages. Attendre N − F réponses plutôt que N, c'est le réflexe des bases répliquées comme des blockchains.
- Raisonner en quorums Deux groupes de plus de N/2 nœuds ont toujours un membre en commun. C'est cette intersection, pas la confiance, qui empêche deux décisions contradictoires.
- Le hasard comme outil Là où aucun algorithme déterministe ne peut conclure à coup sûr, une pièce de monnaie suffit : la sûreté reste garantie, seule la durée devient aléatoire.
- Tester du distribué Dix serveurs, dix ports, des délais : les tests dépendent du temps. Un arrêt propre de chaque nœud (la route /stop) et un délai maximal par test les rendent reproductibles.