Problème des généraux byzantins
Cet article est une ébauche concernant l’informatique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
En informatique, le problème des généraux byzantins est une métaphore qui traite de la 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 publié en 1982[1].
Le problème des généraux byzantins est une généralisation du problème des deux généraux.
Énoncé du problème[modifier | modifier le code]
La métaphore[modifier | modifier le code]
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 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[modifier | modifier le code]
Un ensemble de composants informatiques fonctionnant de concert doit gérer d'éventuelles défaillances parmi ceux-ci. 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'origines accidentelle ou malveillante, intervenant pendant l'établissement des informations ou pendant leur transport d'un composant à l'autre. La gestion de ces composants défectueux est aussi appelée tolérance aux pannes.
Le problème des 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[modifier | modifier le code]
La preuve de travail, et la preuve d'enjeu sont deux types d'algorithme de consensus visant à résoudre les problèmes des généraux byzantins.
Panne byzantine[modifier | modifier le code]
La panne byzantine, ou comportement byzantin, est tout comportement d'un système ne respectant pas ses spécifications, en donnant des résultats non conformes[2],[3].
Les « pannes byzantines naturelles » sont couramment distinguées des « pannes byzantines volontaires » : les premières provenant généralement d'erreurs physiques non détectées (mémoire, transmissions réseaux, etc.), tandis que les secondes sont principalement issues d'attaques visant à faire échouer le système (sabotage, virus, etc.).
L'authentification et la signature par des moyens de cryptographie permettent de limiter les erreurs byzantines.
Notes et références[modifier | modifier le code]
Notes[modifier | modifier le code]
- Cet article est partiellement ou en totalité issu de l'article intitulé « Panne byzantine » (voir la liste des auteurs).
Références[modifier | modifier le code]
- (en) Leslie Lamport, Robert Shostak et Marshall Pease, « The Byzantine Generals Problem », ACM Transactions on Programming Languages and Systems, vol. 4, no 3, (lire en ligne).
- Saber Chabane, Andjima Bouiche, Présentation d'un modèle pour le comportement contradictoire dans les réseaux radio en présence d'un adversaire byzantin, mémoire de fin de cycle en vue de l'obtention de Master 2 en informatique, option : rechercher les réseaux et systèmes distribués, Université A/MIRA de Bejaia, Faculté des sciences exactes, département d'informatique, promotion 2011, p. 17-18 (Panne byzantine ; Classification complémentaire des pannes byzantines).
- Johanne Cohen, « Les pannes Byzantines », sur www.lri.fr (consulté le )
