Byzantinische Fehlertoleranz

Byzantinische Fehlertoleranz ist die Untersuchung der Erzielung von Konsens, wenn einige Prozesse willkürlich ausfallen können, einschließlich durch das Senden widersprüchlicher oder bösartiger Nachrichten.

Definition

Ein byzantinischer Fehler ist eine willkürliche Abweichung von der Spezifikation einer Komponente, einschließlich bösartigen Verhaltens; byzantinische Fehlertoleranz ist die Fähigkeit eines verteilten Protokolls, seine Korrektheitsbedingungen trotz einer begrenzten Anzahl solcher fehlerhaften Teilnehmer zu erfüllen.

Scope

Dieses Thema behandelt das Problem der byzantinischen Generäle und die engen Resilienzgrenzen, die es festlegt (mindestens 3f+1 Prozesse oder signierte Nachrichten, um f beliebige Fehler zu tolerieren), die synchronen Oral- und Signed-Message-Konsensalgorithmen sowie praktische asynchrone byzantinisch fehlertolerante Protokolle wie PBFT und deren Nachfolger. Es bildet die Grundlage für die Vertrauensmodelle von permissioned Blockchains und hochintegren replizierten Diensten.

Core questions

• Wie viele korrekte Prozesse sind erforderlich, um eine gegebene Anzahl beliebiger Fehler zu tolerieren?
• Wie verändern digitale Signaturen die Resilienzgrenzen für den byzantinischen Konsens?
• Wie kann der byzantinische Konsens für praktische asynchrone Systeme effizient genug gestaltet werden?

Key theories

Grenze der byzantinischen Generäle

Bei unauthentifizierten (mündlichen) Nachrichten ist der byzantinische Konsens genau dann lösbar, wenn mehr als zwei Drittel der Prozesse korrekt sind (n > 3f); authentifizierte Nachrichten mit unfälschbaren Signaturen lockern diese Anforderung.

Praktische BFT-Replikation

PBFT zeigt, dass der byzantinische Konsens in einem partiell synchronen System mit Zustandsmaschinenreplikation unter Verwendung eines Primärsystems und eines Dreiphasenprotokolls ablaufen kann, wodurch eine praktische Leistung erzielt wird, während bis zu ein Drittel fehlerhafter Replikate toleriert werden.

Synchrone Konsensalgorithmen

Im synchronen Modell erreichen rekursive Oral-Message- und Signed-Message-Algorithmen den Konsens in f+1 Runden, was die Rundenkomplexitätskosten der Tolerierung beliebiger Fehler veranschaulicht.

Clinical relevance

Byzantinische Fehlertoleranz ist die Grundlage von Systemen, die nicht nur Abstürzen, sondern auch Kompromittierung oder bösartigem Verhalten standhalten müssen, einschließlich permissioned Blockchains, hochsicheren replizierten Diensten sowie Avionik- und Luft- und Raumfahrtsteuerungen, bei denen ein willkürlicher Komponentenausfall nicht ausgeschlossen werden kann.

History

Pease, Shostak und Lamport legten 1980 die Konsensgrenzen fest und dramatisierten sie 1982 als das Problem der byzantinischen Generäle; fast zwei Jahrzehnte lang galt der byzantinische Konsens als zu kostspielig für die Praxis, bis Castros und Liskovs PBFT von 1999 eine effiziente asynchrone byzantinische Replikation demonstrierte, die das Feld wiederbelebte und später den Blockchain-Konsens beeinflusste.

Key figures

• Leslie Lamport
• Robert Shostak
• Marshall Pease
• Miguel Castro
• Barbara Liskov

Seminal works

• lamport1982byz
• castro1999
• pease1980

Frequently asked questions

Warum erfordert die Tolerierung von f byzantinischen Fehlern 3f+1 Prozesse?

Korrekte Prozesse müssen eine Mehrheitsentscheidung treffen, selbst wenn f fehlerhafte Prozesse lügen und weitere f langsam oder unerreichbar sein können; nur mit mehr als der dreifachen Anzahl fehlerhafter Prozesse kann die korrekte Mehrheit die Kombination aus fehlerhaften und verzögerten Teilnehmern immer überstimmen.