Byzantinische Fehlertoleranz (BFT)
1982-07-01
- Leslie Lamport
- Robert Shostak
- Marshall Pease
BFT (Akronym Byzantinische Fehlertoleranz ist eine Eigenschaft eines Systems, die es ihm ermöglicht, weiterhin korrekt zu funktionieren und einen Konsens zu erzielen, selbst wenn einige seiner Komponenten auf beliebige und unvorhersehbare Weise ausfallen, einschließlich böswilligen Verhaltens (byzantinische Ausfälle). Dies ist eine wesentlich stärkere Garantie als die Tolerierung einfacher Systemabstürze. Sie erfordert mindestens 3f+1 Komponenten, um f fehlerhafte, böswillige Komponenten zu tolerieren.
Byzantinische Fehlertoleranz (BFT) befasst sich mit dem „Problem der byzantinischen Generäle“, einem Gedankenexperiment, in dem loyale Generäle einer byzantinischen Armee sich auf einen gemeinsamen Schlachtplan einigen müssen, während sie über potenziell verräterische Boten kommunizieren. Einige Generäle könnten Verräter sein und aktiv versuchen, den Plan durch widersprüchliche Informationen zu sabotieren. BFT-Algorithmen bieten eine Lösung für dieses Problem im verteilten Rechnen und gewährleisten, dass alle fehlerfreien (loyalen) Knoten trotz der Anwesenheit fehlerhafter (verräterischer) Knoten, die lügen, sich absprechen oder willkürlich handeln können, zum selben Ergebnis gelangen.
The seminal 1982 paper by Lamport, Shostak, and Pease proved that for a system to tolerate [latex]f[/latex] Byzantine faults, there must be at least [latex]3f+1[/latex] total nodes (or generals). This means that to tolerate one malicious actor, a system needs at least four nodes in total. The core of BFT algorithms involves multiple rounds of message passing among the nodes. In each round, nodes exchange their current state or proposed value, along with the messages they have received from other nodes. This allows loyal nodes to cross-check information and identify inconsistencies, eventually converging on a single, correct value that is agreed upon by the majority.
Early BFT algorithms, like Practical Byzantine Fault Tolerance (PBFT), were computationally expensive and had high communication overhead, limiting their scalability. However, their ability to provide safety and liveness in an adversarial environment was revolutionary. The rise of blockchain technology in the late 2000s created a massive new application area for BFT. Consensus mechanisms in cryptocurrencies like Bitcoin (using Proof-of-Work, a probabilistic form of BFT) and newer Proof-of-Stake systems (often using explicit BFT protocols like Tendermint or HotStuff) rely on these principles to ensure the integrity and immutability of the distributed ledger, even if a significant fraction of network participants are malicious.
UNESCO Nomenclature: 1203
- Computerwissenschaften
Verwendung
Weitverbreitete Verwendung
Vorläufer
- General research on distributed computing and consensus problems
- Fail-stop fault models (which BFT extends)
- Cryptography and digital signature concepts for message authentication
- Network theory and graph theory
Anwendungen
- blockchain and cryptocurrency protocols (e.g., proof-of-stake consensus)
- distributed databases
- aerospace systems (e.g., boeing 777 flight control systems)
- cloud computing infrastructure
- intrusion detection systems
Potenzielle Innovationsideen
Aufgrund des hohen Datenverkehrs durch Web-Scraping-Bots, der derzeit mehr als 40.000 Anfragen pro Tag umfasst, ist dieser Inhalt ausschließlich Community-Mitgliedern vorbehalten.
> Anmelden < oder > Registrieren < (100% kostenlos) Zugriff darauf sowie auf alle anderen eingeschränkten Inhalte und Tools.
Verwandt mit: byzantinischer Fehlertoleranz, BFT, verteilter Konsens, Problem der byzantinischen Generäle, Blockchain, Leslie Lamport, verteilte Systeme, Fehlertoleranz, böswillige Akteure, PBFT.