In a Byzantine fault model, nodes can do anything: lie, send conflicting messages, collude. This is much stronger than the crash-fault model where nodes simply stop.
Byzantine fault tolerance (BFT) is harder, more expensive, and rarely needed. But when you need it (cryptocurrency, certain financial systems, adversarial environments), nothing else works.
Lamport, Shostak, Pease (1982): generals must agree on attack/retreat. Some generals may be traitors sending conflicting messages.
Result: with f traitors, need at least 3f+1 total generals to reach consensus.
This is the foundational result of BFT.
Node stops, sends nothing. Detectable (with timeouts).
Most practical systems handle this (Paxos, Raft).
Node fails to send/receive some messages. Subset of crash.
Messages arrive late. Asynchronous protocols handle implicitly.
Node behaves arbitrarily — including malicious behavior.
Hardest model. Most expensive to handle.
In crash-fault model:
In Byzantine:
To tolerate f Byzantine faults, need at least 3f+1 nodes.
Why? With 3f total nodes and f Byzantine:
Need 3f+1 to break the symmetry: any majority decision (2f+1) contains at least f+1 honest nodes.
Castro and Liskov (1999). The breakthrough — first practical BFT for synchronous networks.
Used as the basis for many subsequent BFT systems.
BFT for blockchain. Synchronous voting rounds.
Used in Cosmos, Binance Smart Chain.
Linear message complexity (vs PBFT's quadratic).
Used in Diem (formerly Libra).
HotStuff variant. Eventually became Aptos / Sui.
Byzantine agreement for cryptocurrency. Uses VRFs (verifiable random functions) to select committees.
Asynchronous BFT. No timing assumptions.
Slower but robust.
Message delays bounded. Easier; many BFT protocols assume this.
Eventually synchronous after some unknown time. Most practical model.
No bounds. FLP impossibility: deterministic consensus impossible.
Use randomization to circumvent (Honeybadger).
Public cryptocurrencies. Anyone can join; some will be malicious.
Multi-party financial systems. Each party potentially malicious from others' view.
When parties don't trust each other, BFT formalizes the trust assumptions.
Some military and aerospace applications.
If all nodes are operated by one team, crash-fault tolerance suffices.
Use Raft or Paxos. Much simpler, much cheaper.
Most distributed systems in companies.
Even with multiple parties, if you trust them not to be malicious (just to occasionally fail), you don't need BFT.
The vast majority of distributed systems don't need BFT.
PBFT: O(n²) messages per agreement. Throughput limited.
Modern protocols (HotStuff): O(n) but still expensive vs Raft.
Multiple rounds of cryptographic verification.
More sophisticated protocols. Harder to debug.
BFT typically tops out around 100-1000 nodes. Beyond that, hierarchical or sharded approaches.
BFT relies on:
These let nodes prove they aren't lying about messages.
Tolerates Byzantine faults via incentives + computational cost. Not strictly BFT in the classical sense but achieves similar properties.
Uses Casper FFG (BFT-derived) for finality.
Uses crash-fault Raft by default (private blockchain). BFT optional.
Often use BFT protocols (Tendermint, PBFT variants).
Most operational distributed systems are inside one organization. BFT is overkill.
Some protocols assume adversary is computationally bounded; some assume bounded delays. Get assumptions wrong = security failure.
If "Byzantine" failures arise from common bugs (same software), 3f+1 doesn't help — all f+1 honest nodes have same bug.
This is why diversity (different implementations) matters in some BFT systems.
Synchronous BFT with bad timing assumptions can fail.
BFT protocols are complex. Implementation bugs effectively introduce Byzantine behavior.
The general framework: replicate a deterministic state machine across nodes; consensus on input order.
Both Paxos/Raft (CFT) and PBFT (BFT) can be used as the consensus layer.
SMR with BFT consensus = BFT state machine replication.
Modern blockchain influences:
These work in fully open settings where pure BFT doesn't scale.
For most engineers building distributed systems:
If you think you need BFT, ask: who exactly is the adversary? What's their incentive? Often the answer reveals you can use simpler approaches (auditing, retroactive verification, trust models).
When you genuinely need BFT, use a proven protocol; don't roll your own.