Problème du consensus
Le problème du consensus est un problème fondamental en théorie du calcul distribué. Il consiste pour un ensemble de machines à se mettre d'accord sur une valeur ou, par extension, sur une séquence de valeurs. La résolution du consensus est primordiale pour la coordination des systèmes distribués. Elle permet notamment la consistance des systèmes répliqués malgré la défaillance d'une partie de leurs composants. Le consensus est notamment utilisé pour la réplication d'automates (State Machine Replication), l'exécution de transactions distribuées ou encore au cœur des services de coordination tels que ZooKeeper. Paxos, Raft et 2PC comptent parmi les algorithmes les plus populaires. Lorsque les pannes sont arbitraires, on parle de consensus Byzantin. Alors que le consensus classique est privilégié au sein des structures contrôlées comme les centres de données, le consensus Byzantin est requis en milieu ouvert dans le contexte des blockchains. PBFT, Tendermint ou encore l'algorithme de Nakamoto résolvent le consensus Byzantin.
Description du problème
Le problème du consensus consiste à concevoir un protocole permettant à un certain nombre de processus de s'accorder sur une valeur unique. Les processus sont sujets à des pannes qui sont de deux types : les pannes bénignes où le processus cesse simplement de fonctionner, et les pannes byzantines ou arbitraires où le processus exécute des opérations arbitraires non prévues par le protocole (volontairement ou non). Les protocoles de consensus doivent être tolérants aux défaillances. Un processus qui ne tombe pas en panne est dit correct.
Formellement, en informatique théorique, un protocole résout le problème du consensus s'il a les propriétés suivantes :
- Terminaison
- Tout processus qui est correct doit finir par décider une valeur.
- Intégrité
- Tout processus qui est correct décide une valeur qui a été proposée par un des processus.
- Accord
- Tous les processus corrects décident la même valeur.
Un protocole qui peut garantir ces propriétés en présence de moins de t pannes est dit t-robuste ou t-resilient.
Consensus binaire et résultat d'impossibilité
Le consensus binaire est le problème du consensus où les processus doivent s'accorder sur une valeur binaire (0 ou 1) en ayant chacun une valeur binaire de départ à proposer. Un des résultats les plus importants de la théorie du calcul distribué, dite impossibilité FLP, est le suivant : Dans un environnement asynchrone où un processus peut faire défaut, le problème du consensus binaire ne peut être résolu par un algorithme déterministe.[1] Ce résultat peut être contourné par l'utilisation d'algorithmes aléatoires qui résolvent le consensus avec probabilité 1 avec un temps d'exécution infini.
Dans les faits, cette impossibilité théorique n'est pas un frein et de nombreux systèmes résolvent le consensus dans des environnements variés.
Nombre de processus fautifs
La résolution du consensus requiert une hypothèse de synchronie. Dans le modèle synchrone, le consensus peut être résolu avec f+1 processus pour tolérer f pannes. Dans le modèle partiellement synchrone, ou avec un détecteur de pannes dont l'exactitude est finalement faible, résoudre le consensus requiert 2f+1 processus.
Dans le modèle synchrone, le consensus Byzantin requiert 2f+1 processus pour tolérer f pannes. Dans le modèles partiellement synchrone, il requiert 3f+1 processus. En rendant impossible l'équivocation des processus, par l'utilisation de composants de confiance comme des enclaves ou une mémoire partagée protégée, le consensus Byzantin peut être résolu avec 2f+1 processus dans le modèle partiellement synchrone.
Références
- (en) Michael J. Fischer, Nancy A. Lynch et Michael S. Paterson, « Impossibility of Distributed Consensus with One Faulty Process », Journal of the ACM, Association for Computing Machinery, vol. 32, no 2, , p. 374–382 (ISSN 0004-5411, DOI 10.1145/3149.214121, lire en ligne, consulté le )
Pour aller plus loin
Portail de l'informatique théorique