Comment des ordinateurs peuvent-ils s'accorder si certains mentent peut-être ?

Avec assez de voix honnêtes, et mieux encore avec des signatures. Des chercheurs ont prouvé que, quand personne ne peut prouver qui a envoyé un message, un groupe ne peut atteindre un accord fiable que s'il compte plus de trois fois plus de membres que de menteurs : au moins 3n+1 participants pour résister à n d'entre eux. Si les messages portent une signature numérique, 3n suffisent. Ce menteur, les informaticiens l'appellent une panne byzantine : un composant qui présente des symptômes différents selon les observateurs, si bien que les autres ne savent même pas s'il est en panne.

La question s'est posée en 1978 avec SIFT, un projet financé par la NASA au SRI International, fondé sur l'idée que plusieurs ordinateurs ordinaires s'échangent des messages pour parvenir à un consensus, même si certains sont défaillants. Pour la rendre plus parlante, Leslie Lamport l'a habillée en allégorie : des généraux encerclent une ville. Ils doivent décider ensemble d'attaquer ou de battre en retraite, et tous doivent être d'accord, car une attaque menée par quelques-uns seulement serait pire qu'une attaque ou une retraite coordonnées. Le hic, c'est qu'un traître peut mentir de façon ciblée : avec quatre généraux pour l'attaque et quatre pour la retraite, un neuvième, déloyal, peut envoyer un vote de retraite à un camp et un vote d'attaque à l'autre, et couper l'armée en deux.

Robert Shostak, qui a le premier formalisé le problème, a montré qu'il fallait au moins 3n+1 participants, et son collègue Marshall Pease a prouvé que ce chiffre était à la fois nécessaire et suffisant, quel que soit le nombre de participants défaillants. Leslie Lamport a ensuite montré qu'avec des signatures numériques, 3n suffisent : pouvoir prouver qui a vraiment envoyé un message permet de se contenter de moins de participants.

Le nom de l'allégorie a sa petite histoire : les généraux étaient à l'origine des commandants de l'armée albanaise, avant d'être rebaptisés « byzantins » sur la suggestion d'un collègue, pour écarter tout risque de froisser qui que ce soit. Ces travaux ont valu à leurs auteurs le prix Edsger W. Dijkstra 2005.