Product Design, Manufacturing & Innovation Resources
Heim » Byzantinische Fehlertoleranz (BFT)

Byzantinische Fehlertoleranz (BFT)

1982-07-01
  • Leslie Lamport
  • Robert Shostak
  • Marshall Pease
Rechenzentrum zur Veranschaulichung der byzantinischen Fehlertoleranz in verteilten Computersystemen.

(Abbildung dient nur zur Veranschaulichung)

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

Typ

Software/Algorithmus

Störung

Inkremental

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

Patente:

NA

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.

Historischer Kontext

Byzantinische Fehlertoleranz (BFT)

1980
1980
1980
1982-07-01
1988-06-01
1990
1993
1975-06-01
1980
1980
1980
1986-01-01
1990
1990
1993

(wenn das Datum unbekannt oder nicht relevant ist, z. B. „Strömungsmechanik“, wird eine gerundete Schätzung seines bemerkenswerten Auftretens bereitgestellt)

Verwandte Erfindungen, Innovationen und technische Prinzipien

Bilder in voller Größe und Downloads sind nur für registrierte Mitglieder 100% kostenlos verfügbar.

> Login <