Consensus (informatique)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Le problème du consensus est un problème fondamental en théorie du calcul distribué. Le principe étant de parvenir à obtenir une certaine fiabilité d'un système dans des problèmes de décision distribuée, en présence de pannes. On peut citer quelques exemples concrets d'applications de ce problème dans les bases de données distribuées, l'élection d'un leader

Description du problème[modifier | modifier le code]

Le consensus demande à ce qu'un certain nombre de processus s'accordent sur une valeur unique. les processeurs peuvent tomber en panne, ou être non-fiables, donc les protocoles de consensus doivent être tolérants aux défaillances

Certaines approches à ce problème ne demandent qu'une majorité de processus qui s'accordent, et la valeur sera tirée par votes.

Formellement, en informatique théorique, le problème du consensus demande un protocole qui réponde aux critères suivants :

Terminaison
Tout processus doit décider une valeur.
Intégrité
Tout processus décide une valeur qui a été proposée par un des processus.
Accord
Tous les processus 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.

==Consensus binaire et résultats 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é est le suivant : :Dans un environnement asynchrone où un processeur peut tomber en panne, le problème du consensus binaire est impossible.[1]

Références[modifier | modifier le code]

  1. (en) Michael J Fischer, « Impossibility of distributed consensus with one faulty process », Journal of the ACM, vol. 32, no 2,‎ avril 1985 (DOI 10.1145/3149.214121, lire en ligne)

Pour aller plus loin[modifier | modifier le code]