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 cohérence 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 et Raft 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. 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èle 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.

Pour aller plus loin

• Type de données répliqué sans conflit : une structure de données qui se synchronise avec plusieurs réplicas sans consensus, ni conflit.
• DOI 10.1145/331524.331529
• DOI 10.1137/S0097539796307698
• DOI 10.1007/978-3-642-15260-3