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 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. 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.