Product Design, Manufacturing & Innovation Resources
Home » Byzantine Fault Tolerance (BFT)

Byzantine Fault Tolerance (BFT)

1982-07-01
  • Leslie Lamport
  • Robert Shostak
  • Marshall Pease
Data center illustrating Byzantine Fault Tolerance in distributed computing systems.

(generated image for illustration only)

BFT (acronym of Byzantine Fault Tolerance) is a property of a system that allows it to continue operating correctly and reach consensus even if some of its components fail in arbitrary, unpredictable ways, including malicious behavior (Byzantine failures). This is a much stronger guarantee than tolerating simple crash failures. It requires a minimum of \(3f+1\) total components to tolerate \(f\) faulty, malicious components.

Byzantine Fault Tolerance addresses the “Byzantine Generals Problem,” a thought experiment where loyal generals of a Byzantine army must agree on a common battle plan while communicating through potentially treacherous messengers. Some generals may be traitors and actively try to foil the plan by sending conflicting information. BFT algorithms provide a solution to this problem in distributed computing, ensuring that all non-faulty (loyal) nodes reach the same conclusion, despite the presence of faulty (traitorous) nodes that can lie, collude, or behave arbitrarily.

The seminal 1982 paper by Lamport, Shostak, and Pease proved that for a system to tolerate \(f\) Byzantine faults, there must be at least \(3f+1\) 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
– Computer science

Type

Software/Algorithm

Disruption

Incremental

Usage

Widespread Use

Precursors

  • 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

Applications

  • 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

Patents:

NA

Potential Innovations Ideas

Due to scrapping bot traffic, currently more than 40k per day, this content is reserved to community members.
> Login < or > Register < (100% free) to access this, so as all other restricted content and tools.

Related to: byzantine fault tolerance, BFT, distributed consensus, byzantine generals problem, blockchain, Leslie Lamport, distributed systems, fault tolerance, malicious actors, PBFT.

Historical Context

Byzantine Fault Tolerance (BFT)

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

(if date is unknown or not relevant, e.g. "fluid mechanics", a rounded estimation of its notable emergence is provided)

Related Invention, Innovation & Technical Principles

Full size images and downloads are only available, 100% free, for registered members.

> Login <