Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Problème du consensus
Résumé
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.