Consensus distribué

Le consensus distribué est le problème qui consiste à faire en sorte qu'un ensemble de processus s'accordent sur une valeur unique malgré les délais de message et les défaillances de processus, et il constitue l'abstraction centrale de l'informatique tolérante aux pannes.

Definition

Le consensus exige que chaque processus non défaillant, à partir d'une entrée proposée, décide finalement d'une valeur de sortie telle que tous les processus non défaillants décident de la même valeur (accord), que la valeur ait été proposée par un processus (validité), et que chaque processus non défaillant décide finalement (terminaison).

Scope

Ce sujet couvre la spécification formelle du consensus (accord, validité, intégrité et terminaison), le théorème d'impossibilité FLP et les moyens de le contourner — synchronie partielle, détecteurs de pannes non fiables et randomisation — ainsi que l'équivalence du consensus avec la diffusion atomique et les machines à états répliquées. Il traite du contexte des pannes par crash ; le contexte byzantin est abordé dans un sujet connexe.

Core questions

• Que doit garantir exactement un protocole pour être un algorithme de consensus correct ?
• Pourquoi le consensus asynchrone déterministe est-il impossible même avec un seul crash ?
• Quelles hypothèses supplémentaires — synchronie, détecteurs de pannes, aléatoire — rétablissent la solubilité ?

Key theories

Impossibilité FLP

Aucun protocole déterministe ne résout le consensus dans un système asynchrone à passage de messages si même un seul processus peut tomber en panne (crash), car chaque protocole possède une exécution qui peut être dirigée pour s'exécuter indéfiniment sans prendre de décision.

Approche par détecteurs de pannes

L'augmentation d'un système asynchrone avec un détecteur de pannes non fiable qui est finalement précis rétablit la solubilité du consensus, et le détecteur le plus faible suffisant a été précisément caractérisé.

Consensus randomisé

Permettre aux processus de tirer à pile ou face (lancer des pièces) permet au consensus de se terminer avec une probabilité de un même dans un système entièrement asynchrone, échangeant la terminaison déterministe contre une terminaison probabiliste pour échapper à la barrière FLP.

Clinical relevance

Tout système distribué fortement cohérent — journaux répliqués, services de coordination, magasins de configuration — résout le consensus en interne, de sorte que les garanties et les limites établies ici déterminent directement ce que de tels systèmes peuvent promettre en termes de cohérence et de disponibilité.

History

Le théorème FLP de 1985 a établi l'impossibilité fondamentale ; le protocole randomisé de Ben-Or de 1983 et le cadre des détecteurs de pannes de Chandra et Toueg de 1996 ont ensuite montré deux approches complémentaires pour rendre le consensus soluble, définissant ainsi l'agenda de recherche pour les décennies suivantes.

Key figures

• Michael Fischer
• Nancy Lynch
• Michael Paterson
• Tushar Chandra
• Sam Toueg
• Michael Ben-Or

Seminal works

• fischer1985
• chandra1996
• ben-or1983

Frequently asked questions

Si le consensus est impossible, comment les systèmes réels y parviennent-ils ?

L'impossibilité ne s'applique qu'à un protocole déterministe qui doit toujours se terminer dans un modèle entièrement asynchrone. Les systèmes réels maintiennent la sûreté inconditionnelle et s'appuient sur une synchronie éventuelle ou sur l'aléatoire pour la terminaison, de sorte qu'ils ne violent jamais l'accord et progressent chaque fois que le réseau se comporte correctement.