- Problème des généraux byzantins
-
Le problème des généraux byzantins est une métaphore qui traite de remise en cause de la fiabilité des transmissions et de l'intégrité des interlocuteurs. La question est donc de savoir comment, et dans quelle mesure, il est possible de prendre en compte une information dont la source ou le canal de transmission est suspect. La solution implique l'établissement d'un algorithme (d'une stratégie) adapté. Ce problème a été traité en profondeur pour la première fois dans l'article The Byzantine Generals Problem[1].
Sommaire
Énoncé du problème
La métaphore
Des généraux de l'armée byzantine campent autour d'une cité ennemie. Ils ne peuvent communiquer qu'à l'aide de messagers et doivent établir un plan de bataille commun, faute de quoi la défaite sera inévitable. Cependant un certain nombre de ces généraux peuvent s'avérer être des traîtres, qui essayeront donc de semer la confusion parmi les autres. Le problème est donc de trouver un algorithme pour s'assurer que les généraux loyaux arrivent tout de même à se mettre d'accord sur un plan de bataille.
Il a été démontré qu'en utilisant uniquement des messages oraux, ce problème des généraux byzantins peut être résolu, si et seulement si plus des deux tiers des généraux (messagers) sont loyaux. Ainsi un seul traître peut confondre deux généraux loyaux. De plus, le problème peut être résolu pour un nombre quelconque de généraux renégats si les messages sont écrits (et non falsifiables).
L'analogie avec les systèmes informatiques
Un ensemble de composants informatiques fonctionnant de concert doivent gérer d'éventuelles défaillances parmi eux. Ces défaillances consisteront alors en la présentation d'informations erronées ou incohérentes. On s'intéresse ici à des problèmes de défaillances, aussi bien matérielles que logicielles, d'origine accidentelle ou malveillante, intervenant pendant l'établissement des informations ou pendant leurs transports d'un composant à l'autre. La gestion de ces composants défectueux est aussi appelée tolérance aux pannes.
Le problème de composants défectueux dans un système informatique (ou ailleurs) peut être exprimé de façon abstraite en termes de généraux de l'armée byzantine.
Étude algorithmique
Références
- The Byzantine Generals Problem, Leslie LAMPORT, Robert SHOSTAK, Marshall PEASE, ACM Transactions on Programming Languages and Systems, Vol. 4, No. 3, juillet 1982.
Liens externes
Wikimedia Foundation. 2010.
