Pourquoi un seuil est-il déterminé pour la tolérance aux défaillances byzantines d'un réseau "asynchrone"?(où il ne peut pas tolérer même un nœud défectueux)

Question

Dans la réponse suivante ( Link: https://bitcoin.stackexchange.com/a/ 58908/41513 ), il a été montré que pour Accord asynchrone byzantine :

"Nous ne pouvons tolérer que 1/3 ou plus des nœuds étant malhonnêtes ou que nous perdons soit la sécurité ou la vie. "

Pour cette preuve, les conditions / exigences suivantes ont été envisagées:

1. Notre système est asynchrone .
2. Certains participants peuvent être malveillants.
3. Nous voulons la sécurité.
4. nous voulons de la vie.

Une question fondamentale est que:

Avec considérant le document bien connu intitulé: "impossibilité de consensus distribué avec un processus défectueux" ( link: https://apps.dtic.mil/dtic/tr/fulltext/u2/a132503.pdf ) < / p>

montrant que:

Aucun protocole de consensus totalement asynchrone ne peut tolérer même un seul processus de processus inannoncé ,

Peut-on quand même supposer que le réseau est asynchrone? Comme dans ce cas, le réseau ne peut tolérer qu'un nœud défectueux.

Answer 1

La réponse concerne le suivi des hypothèses précises effectuées dans ces différents résultats. En bref, alors que les deux résultats supposent que l'asynchronie, l'impossibilité de consensus distribué avec un processus défectueux »nécessite une forme de force et de déterminisme plus forte, ce qui rend un consensus impossible.

1. Impossibilité de consensus distribué avec un processus défectueux

Ce résultat séminal (de Michael Fischer, Nancy Lynch et Michael Paterson) est à propos du consensus distribué où le système n'est pas simplement asynchrone, mais également satisfait:

• déterminisme. L'algorithme de consensus n'utilise aucun alumité.

• véridique sous les délais de message. Non seulement les messages peuvent être retardés de manière arbitraire, mais nous devons également garantir la vie même en présence de tels retards continus.

Voyons pourquoi TeeSe Properties sont trop forts et faire un consensus distribué impossible.

Considérez un exemple: Alice, Bob et Charlie sont amis et veulent décider où se rencontrer pour le dîner. Il est possible que l'un d'entre eux vaut inopinément awol (ou décide qu'ils ne veulent plus être amis) et cesse de répondre aux messages. Dans ce cas, les deux autres peuvent toujours décider d'un endroit à rencontrer. Maintenant, que devraient-ils faire?

L'approche évidente serait que:

Alice décide simplement de savoir où aller et raconte Bob et Charlie.

Mais cela ne fonctionne pas car Alice peut être celui qui va awol. Donc, pour résoudre ce problème, la prochaine approche la plus évidente pourrait être:

Alice et Bob disent à tous les autres où aller. Si tout le monde entend d'Alice, ils iront là où Alice dit; Sinon, ils iront où dit Bob.

Mais cela a un nouveau problème. Supposons que tu sois Charlie. Si vous entendez Alice, vous savez où aller. Si vous n'entendez aucun d'aucun d'eux, vous attendez d'entendre. Le problème est que lorsque vous avez entendu parler de Bob, mais pas Alice. Parce qu'il y a des retards de message arbitraires, vous ne pouvez pas vous engager d'aller où Bob a dit: Alice aurait pu dire où aller et vous ne l'avez pas encore reçu! Donc, vous êtes complètement coincé, et s'il arrive que Alice a devenu Awol, vous continuerez à attendre pour toujours.

Le problème ici est que nous n'avons aucun moyen d'abandonner la transaction; Pas moyen de dire: "Ok, cela ne fonctionne pas, ça fait trop longtemps et je n'ai pas reçu de retard - essayons à nouveau." Les algorithmes de consensus réels mondiaux (les Paxos les plus connus) ont la possibilité que des rondes échouent en raison des retards de réseau et, dans ce cas, ils réessayent à nouveau, dans l'espoir de retards de réseau plus courts. De plus, il est possible de contourner le problème en utilisant des protocoles randomisés qui habituellement fonctionne et ne vont que pour toujours avec une faible probabilité (ou même égale à zéro).

2. Accord asynchrone byzantin où moins que 1/3 $ des nœuds échoue

L'article BitCoinse Vous liez les glosses sur la question de la vie, en disant que c'est «la capacité de continuer à faire progresser les progrès». En fait, le résultat ci-dessus montre que la forme la plus forte de cela est impossible, nous devons donc nous détendre nos exigences / hypothèses.

Considérons deux exemples. À Miguel Castro et à Barbara Liskov "la tolérance de défauts de Byzantine" de Barbara Liskov, ils obtiennent une vie pratique avec moins d'un tiers des nœuds défectueux par supposant que les retards de message ne continuent pas à croître indéfiniment . Comme les auteurs énoncent:

Nous garantissons de la vie, c'est-à-dire des clients recevoir finalement des réponses à leurs demandes, fournies au plus $ \ frac {n-1} {3} $ Les répliques sont défectueuses et $ (t) $ ne fait pas croître plus vite que $ t $ indéfiniment ... c'est une synchronisation plutôt faible hypothèse susceptible d'être vraie dans tout système réel des défauts de réseau fournis sont finalement réparés, mais il nous permet de contourner le résultat impossibles dans [9].

ici [9] est le résultat impossible discuté ci-dessus. En termes simples pour notre exemple, ils évitent le problème ci-dessus avec Charlie en nécessitant une forme de synchronisation faible: Charlie ne doit pas simplement continuer à attendre éternellement, car nous savons que les retards de message ne peuvent que croître à la norme et non indéfiniment. (Bien sûr, l'algorithme réel devient beaucoup plus complexe, mais c'est en partie l'idée conceptuelle de la raison pour laquelle la vie est possible.)

Dans Ran Canetti et Tal Rabin's "Accord asynchrone asynchrone de Tal Rabin avec une résilience optimale", ils utilisent le hasard pour obtenir de la vraie avec moins de $ n / 3 $ échecs de nœud byzantine . De leur papier:

Dans ce réglage, nous décrivons une $ (\ lceil \ frac {n} {3} \ rcil- 1) $ - Protocole d'accord byzantin. Avec probabilité accablante que tous les joueurs non défectueux complètent l'exécution

du protocole.Conditionné sur le événement que tous les joueurs non défectueux ont terminé la L'exécution du protocole, ils le font en constante temps.

ici $ (\ lceil \ frac {n} {3} \ rcil- 1) $ -Resilient signifie que moins d'un tiers des nœuds sont byzantins. Notez les mots clés avec une probabilité accablante. Ils ont donc un algorithme probabiliste qui a de nombreuses "pistes" possibles et la plupart d'entre eux travaillent.Notez que le résultat impossibles ci-dessus implique qu'il doit toujours être quelques-uns les courses où la profonde ne se produit pas, c'est-à-dire qu'il n'y a pas de consensus:

Fischer, Lynch et Paterson [FLP] L'impossibilité de la séminale des protocoles déterministes implique que tout protocole (randomisé) atteignant BA doit avoir des courses non déroulantes.