Problème des deux généraux
From Wikipedia, the free encyclopedia
Cet article est une ébauche concernant l’informatique.
En informatique, le problème des deux généraux, aussi appelé problème des deux armées, est une expérience de pensée censée mettre en évidence les limites d'un médium non fiable et asynchrone pour mettre au point une action coordonnée. Il est relié au problème plus général des généraux byzantins, qui a été énoncé postérieurement[1]. En logique épistémique, le concept crucial mis en œuvre est celui de la connaissance commune.
Deux corps d'armée W et B sont situés à une certaine distance l'un de l'autre et doivent attaquer une armée N[2]. Ensemble, les deux corps d'armée peuvent vaincre l'armée de N. Isolément, chacun serait défait. Aucun d'eux ne pouvant attaquer seul, les généraux commandant les corps d'armée doivent coordonner leur attaque. Autrement dit, ils doivent se mettre d'accord sur le jour et sur l'heure de leur attaque. Or, ils ne communiquent que par des messagers (disons à cheval) qui mettent un certain temps (asynchronisme) pour rejoindre le camp de l'autre général et peuvent être capturés par l'ennemi (absence de fiabilité). Comment doivent-il faire ?
L'impossibilité de la coordination
Supposons que le général W prenne l'initiative et fixe le jour et l'heure de l'attaque[3]. Pour informer le général B, il lui envoie un messager qui mettra un quart d'heure pour le joindre et risque d'être capturé. Le général W n'attaquera que s'il a l'agrément du général B, agrément qui doit aussi lui parvenir par un messager, lequel mettra, à nouveau, un quart d'heure pour lui transmettre l'accusé de réception, s'il n'est pas fait prisonnier. De même, le général B n'attaquera pas seul et ne le fera que s'il sait, à travers un accusé de réception envoyé par un messager, que le général W a bien reçu son accord. Mais alors, pour que le général W attaque, il faut qu'il sache que B a bien reçu son accusé de réception. Mais le général B n'attaquera que s'il a reçu l'accusé de réception de l'accusé de réception. On voit que d'accusés de réception en accusés de réception, une coordination nécessite un temps infini et n'est donc pas possible.
Pour résumer, afin que l'attaque ait lieu, il faut que le général W sache que le général B sait que le général W sait que le général B sait, et ainsi de suite. L'acquisition de cette information itérée par W et B s'appelle la connaissance commune. L'impossibilité de l'attaque coordonnée dit que l'acquisition de cette connaissance commune est impossible en employant des messagers ou des messages sur Internet, ou encore que la connaissance commune ne peut s'acquérir par transmissions « asynchrones » et « non fiables ».
