Warum ist eine Schwelle, die für byzantinische Fehlertoleranz eines "asynchronen" Netzwerks bestimmt wird?(wo es nicht einmal einen fehlerhaften Knoten tolerieren kann)

Question

In der folgenden Antwort ( link: https://bitcoin.steckexchange.com/a/ 58908/41513 ), es wurde gezeigt, dass für asynchrone byzantinische Vereinbarung :

"Wir können 1/3 oder mehr der Noten nicht tolerieren, die unehrlich sind oder wir verlieren entweder Sicherheit oder Lektivität. "

Für diesen Nachweis wurden folgende Bedingungen / Anforderungen berücksichtigt:

.
1. Unser System ist asynchron .
2. Einige Teilnehmer können böswillig sein.
3. Wir wollen Sicherheit.
4. Wir wollen das Livität.

Eine grundlegende Frage ist, dass:

Mit Blick auf das bekannte Papier mit dem Titel: "Unmöglichkeit des verteilten Konsenses mit einem fehlerhaften Prozess" ( link: https://apps.dtic.mil/dtic/tr/tfulltext/u2/a132503.pdf ) < / p>

zeigt das:

kein vollständiges asynchrones Konsenprotokoll kann sogar einen einzigen unangemeldeten Prozess tolerieren ,

Können wir immer noch davon ausgehen, dass das Netzwerk asynchron ist? Wie in diesem Fall kann das Netzwerk nicht auch einen fehlerhaften Knoten tolerieren.

Answer 1

Die Antwort hat mit der Verfolgung der genauen Annahmen, die in diesen verschiedenen Ergebnissen hergestellt werden. Kurz gesagt, während beide Ergebnisse Asynchrony übernehmen, erfordert die "Unmöglichkeit des verteilten Konsenses mit einem fehlerhaften Prozess" eine stärkere Form von Livität und Determinismus, und das macht Konsens unmöglich.

1. Unmöglichkeit des verteilten Konsenses mit einem fehlerhaften Prozess

Dieses Seminal-Ergebnis (von Michael Fischer, Nancy Lynch, und Michael Paterson) geht es um verteilte Konsens, bei der das System nicht nur asynchron ist, sondern auch erfüllt:

• determinismus. Der Konsensalgorithmus verwendet keine Zufälligkeit.

• Livität unter Nachrichtenverzögerungen. Nicht nur können Nachrichten willkürlich verzögert werden, aber wir müssen auch bei Anwesenheit solcher fortgesetzter Verzögerungen das Livität garantieren.

Lassen Sie uns sehen, warum Tehse-Eigenschaften zu stark sind und den verteilten Konsens unmöglich machen.

Betrachten Sie ein Beispiel: Alice, Bob und Charlie sind Freunde und möchten entscheiden, wo Sie zum Abendessen treffen können. Es ist möglich, dass einer von ihnen unerwartet Awol geht (oder entscheidet, dass sie nicht mehr daran interessiert sind, mehr Freunde zu sein) und nicht mehr auf Nachrichten reagieren. In diesem Fall können die anderen beiden immer noch an einem Ort entscheiden, an dem sich erfahren. Nun, was sollen sie tun?

Der offensichtliche Ansatz wäre das:

Alice entscheidet einfach, wohin ich gehen soll, und sagt Bob und Charlie.

Das funktioniert jedoch nicht, weil Alice derjenige sein kann, der Awol geht. Um dies zu beheben, könnte der nächstliegende Ansatz sein:

Sowohl Alice als auch Bob erzählen alle anderen, wo sie gehen können. Wenn jeder von Alice hört, gehen sie dorthin, wo Alice sagt. Ansonsten werden sie gehen, wo Bob sagt.

Das hat jedoch ein neues Problem. Angenommen, Sie sind Charlie. Wenn Sie von Alice hören, wissen Sie, wo Sie gehen sollen. Wenn Sie von keiner von ihnen hören, warten Sie, um zu hören. Das Problem ist, wenn Sie von Bob gehört haben, aber nicht Alice. Da es willkürliche Botschaftsverzögerungen gibt, können Sie nicht verpflichten, zu gehen, wo Bob sagte: Alice hätte vielleicht gesagt, wohin man gehen soll, und Sie haben es noch nicht erhalten! Sie sind also völlig fest, und wenn es passiert, dass Alice Awol gegangen ist, werden Sie einfach immer auf immer warten.

Das Problem hier ist, dass wir keine Möglichkeit haben, die Transaktion abzubrechen. Auf keinen Fall zu sagen: "Ok, das funktioniert nicht, es ist zu lang, und ich habe keine Verzögerung erhalten - versuchen wir es noch einmal." Real-World Consenser Algorithmen (das bekannteste Sein Paxos) hat die Möglichkeit, dass Runden aufgrund von Netzwerkverzögerungen versagen, und in diesem Fall versuchen sie einfach erneut, in der Hoffnung auf kürzere Netzwerkverzögerungen. Darüber hinaus ist es möglich, das Problem durch die Verwendung randomisierter Protokolle zu erhalten, die in der Regel funktionieren, und nur für immer mit einer kleinen (oder sogar Null-) Wahrscheinlichkeit weitergehen.

2. Asynchrone byzantinische Vereinbarung, bei der weniger als $ 1/3 $ der Knoten fehlschlägt

Der Bitcoinse-Beitrag, den Sie mit der Verknüpfung von Glanz über das Problem der Lebendigkeit verknüpfen und nur sagen, dass es "die Fähigkeit, Fortschrittsfortschritte weitermachen" zu sagen. In der Tat zeigt das obige Ergebnis, dass die stärkste Form davon unmöglich ist, also müssen wir unsere Anforderungen / Annahmen entspannen.

Betrachten wir zwei Beispiele. In Miguel Castro und Barbara Liskovs "praktische byzantinische Fehlertoleranz" erreichen sie praktische Lebendigkeit mit weniger als einem Drittel der Knoten, die von angenommen werden, wenn die Nachrichtenverzögerungen nicht auf unbestimmte Zeit wachsen . Wie die Autoren staatlich:

Wir garantieren die Lektivität, d. H., Kunden Erhalten Sie schließlich Antworten auf ihre Anfragen, die höchstens angeboten werden $ \ frac {n-1} {3} $ replikas sind fehlerhaft und $ delay (t) $ nicht schneller wachsen als $ t $ unbegrenzt ... Dies ist eine ziemlich schwache Synchronisation Annahme, dass in einem echten System wahrscheinlich erfüllt ist Bereitstellten Netzwerkfehler werden schließlich repariert, doch es Ermöglicht uns, die Unmöglichkeit in Bezug auf [9] zu umgehen.

Hier [9] ist das oben diskutierte Unmöglichkeitsergebnis. In schimmerndem Beispielen für unser Beispiel vermeiden sie das obige Problem mit Charlie, indem sie eine schwache Synchronitätsform erfordern: Charlie muss nicht einfach auf immer warten, da wir wissen, da wir wissen, dass Nachrichtenverzögerungen nur ursprünglich wachsen können, und nicht unbegrenzt. (Natürlich wird der eigentliche Algorithmus viel komplexer, aber das ist zum Teil die konzeptionelle Idee, warum das Livität möglich ist.)

in Ran Canetti und Tal Rabins "Fast asynchrones byzantinisches Abkommen mit optimaler Widerstandsfähigkeit", verwenden sie Zufälligkeit, um mit weniger als $ n / 3 $ byzantinische Knotenausfälle zu leiden . Von ihrem Papier:

In dieser Einstellung beschreiben wir einen $ (\ lceil \ frac {n} {3} \ RCEIL- 1) $ -ressilient Byzantinische Vereinbarungsprotokoll. Mit Überwältigende Wahrscheinlichkeit Alle nicht fehlerhaften Spieler vervollständigen die Ausführung

des Protokolls.Konditioniert auf dem Ereignis, dass alle nicht fehlerhaften Spieler das abgeschlossen haben Ausführung des Protokolls, tun sie dies in konstantem voraussichtlich Zeit.

hier $ (\ lceil \ frac {n} {3} \ rceil- 1) $ -ressilient bedeutet nur weniger als ein Drittel der Knoten sind byzantinisch. Beachten Sie die Schlüsselwörter mit überwältigender Wahrscheinlichkeit. Daher haben sie einen probabilistischen Algorithmus, der viele mögliche "Läufe" aufweist, und die meisten von ihnen funktionieren überwältigend.Beachten Sie, dass das obige Unmöglichkeitsergebnis impliziert, dass es immer einige läuft, in denen das Livität nicht auftritt, d. H. Es gibt keinen Konsens:

Fischer, Lynch und Patersons [FLP] Seminal Unmöglichkeitsergebnis für deterministische Protokolle impliziert, dass ein beliebiges (randomisiertes) Protokoll, das BA erreicht, nichtminierende Läufe haben muss.