Quel est le problème des généraux byzantins ?

Le problème des généraux byzantins est une expérience de pensée qui traite d'une question clé de l'informatique : est-il possible de former un consensus dans un réseau informatique composé de nœuds indépendants et géographiquement répartis ?

Le problème a été proposé en 1982 par des chercheurs du SRI International Research Institute.

Cela se déroule comme suit : un certain nombre de généraux byzantins assiègent une ville. Ils ne peuvent communiquer qu’en s’envoyant des messagers. Les généraux doivent se mettre d'accord sur un plan d'action commun : attaquer la ville ou battre en retraite. Cependant, certains généraux sont des traîtres et s’opposent activement à la formation d’un consensus ; leur nombre et leur identité sont inconnus.

La question posée par le problème est de savoir quel algorithme de prise de décision les généraux devraient utiliser pour élaborer un plan commun – indépendamment de l'interférence des traîtres – et si un tel algorithme existe.

Selon l'analyse des chercheurs, un tel système est effectivement réalisable, mais le nombre de généraux fidèles doit strictement dépasser les deux tiers. Par exemple, dans une situation où il y a trois généraux, dont un traître, les plus loyaux ne peuvent jamais garantir qu’ils parviendront à un consensus.

Ce problème est particulièrement pertinent pour les crypto-monnaies car il s’agit par essence de systèmes informatiques distribués : ils sont composés de nœuds de traitement des transactions indépendants les uns des autres et de toute autorité centrale et ne peuvent communiquer qu’à distance. Ce sont les « généraux » qui doivent parvenir à un consensus sur les transactions qui ont eu lieu et à quel moment.

Les nœuds peuvent potentiellement fournir des données erronées sur les transactions, soit par choix, soit par accident, et leurs informations doivent être triées. Bitcoin (BTC) et d’autres crypto-monnaies résolvent ce problème via des solutions techniques telles que les algorithmes de preuve de travail et de preuve de participation.

Voir Tolérance aux pannes byzantine (BFT).