Impossibilité du consensus: Fischer, Lynch et Paterson.
Quelques idées
La preuve de FLP repose sur l'utilisation du graphe d'exécution d'un protocole de consensus binaire quelconque.
Le problème du consensus binaire est une restriction du problème du consensus général
au cas où l'ensemble des valeurs initiales des processus est l'ensemble {0,1}.
A chaque sommet du graphe, on associe sa valence. La valence d'un sommet du graphe
est l'ensemble des valeurs qui peuvent être décidée à partir de ce sommet. De par la
définition même du problème c'est un sous-ensemble, non vide, de {0,1}. L'étiquetage complet
de l'arbre respecte certaines propriétés qui permettent d'en dériver une
contradiction quant à l'existence d'un algorithme déterministe permettant de résoudre
le consensus binaire, et par extension le consensus.
Pour aller plus loin
J'ai réalisé des transparents qui présentent de manière détaillée
la preuve complète. Vous pouvez les obtenir en Français:
Je les ai réactualiser et compléter pour un cours que j'ai donné devant les membres
du Lasid, à l'Université Fédérale de Bahia (Brésil). Vous pouvez les
obtenir (en Anglais seulement):
Frédéric Tronel
Last modified: Fri Oct 12 17:33:00 MEST 2001
