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.

De ce problème vient le nom de panne byzantine, si sur un réseau un nœud présente un comportement byzantin c'est qu'il ne suit pas sa spécification et envoie des données erronées ou pas de données du tout. Il peut être vu comme dysfonctionnel par certains de ses voisins et comme fonctionnel par d'autres. Cela peut être le signe d'un problème matériel ou d'une action malveillante.

Applications Concrètes

La tolérance aux pannes byzantines est utile dans les systèmes distribués, par exemple:

• Redondance pour un système critique: Dans l’aérospatiale on trouve plusieurs exemple de BFT car certains systèmes critiques sont dupliqués pour réduire la probabilité de défaillance de l'appareil. Ces systèmes dupliqués doivent donc arriver à un consensus.
• Base de données distribuées: Répartir une base de données sur plusieurs data centers permet d'assurer redondance, tolérance au pannes et disponibilité il faut cependant que la base de données contenue dans chaque data center soit identique.
• BlockChain (ex: bitcoin): Le système bitcoin est un base de données décentralisée contenant toutes les transactions ayant eut lieu sur le réseau. Chaque utilisateurs a une version locale de cette liste de transaction et chaque utilisateur doit avoir la même version.