VT2020-BFT-Fiche

Abstract

L'Utilisation de plus en plus rependue de systèmes distribués nous force à considérer le problème du consensus au sein d'un réseau. Comment un groupe de machine arrive t'il à s’accorder sur l'état d'une base de données quand chacune des machines du réseau en a sa propre version, que le réseau ne garantis aucune fiabilité et que les machines composant le réseau sont elles-mêmes faillibles?

Le Problème des deux Généraux

Définition

Soient deux armées A et B encerclant une armée C. A et B doivent se mettre d'accord sur un heure à laquelle attaquer C ou prendre la décision de se replier. Pour "gagner" il faut que les armées A et B attaquent simultanément ou se replient toute les deux. Si l'attaque est désynchronisée ou qu'une armée se replie tandis que l'autre attaque, la défaite est assurée. C'est donc le consensus entre A et B qui déterminera l'issue du combat.

Pour communiquer, A et B s'envoient des messagers qui doivent traverser le territoire adverse. On ne peut garantir que le messager arrivera à destination, ce n'est donc pas un canal de communication fiable. Il faut cependant trouver un protocole de communication permettant aux deux armées d'arriver à un accord.

Impossibilité

Si on considère un protocole inspiré de TCP et notamment des messages échangés lors de l'ouverture d'un connexion (SYN, SYN-ACK, ACK), on obtient un protocole qui se déroule comme suit:

Si lors du premier message A n'attends pas acquittement, il sera seul face à l'ennemi si son message est perdu. On trouve la situation inverse si A attends un acquittement mais pas B, si le deuxième message se perd, A continuera d'attendre pendent que B perd la bataille. En fait on peu continuer d'ajouter des message à ce dialogue pour acquitter les acquittements, l'engagement d'une armée ou de l'autre à rentrer dans la bataille repose toujours sur le dernier message de la conversation, et ce dernier peut toujours être perdu. Il n'y a pas de solution déterministe à ce problème.

Le Problème des Généraux Byzantins

Définition

Le problème des généraux Byzantins permet de généraliser le problème des deux généraux à un plus nombre n de généraux.

Soient n généraux encerclant une ville, ils doivent s'accorder sur la stratégie à adopter pour leur assaut: attaquer ou se replier. Pour communiquer, ils s'envoient des messagers qui peuvent se faire capturer par l'ennemi ou même être remplacé par un messager à la solde de l'ennemi et transportant un message contrefait. De plus il est possible que des généraux soient des traîtres et tentent d’empêcher le consensus en envoyant des messages erronés aux autres généraux.

Pour gagner il faut que tout les généraux loyaux parviennent à un consensus, si seule une partie des généraux loyaux passent à l'attaque, la défaite et inévitable. Il faut donc un protocole permettant le consensus malgré la présence de traîtres et les canaux de communication peu fiables.