Practical Byzantine Fault Tolerance
Miguel Castro, Barbara Liskov2002ACM TOCS 2002
Read it on doi.org(opens in a new tab)Why this one
Read this after The Byzantine Generals Problem and Impossibility of Distributed Consensus with One Faulty Process. Those papers teach you why agreement is hard when machines lie or disappear. Castro and Liskov show what it takes to turn that theory into a replicated service you could actually run. The key idea is not magic cryptography or blockchain folklore, it is disciplined message phases, view changes, and careful engineering around the common case. People often remember PBFT as "3f plus 1 replicas" and miss the systems lesson: safety is only useful if the protocol also keeps latency, signatures, checkpoints, and recovery under control. If you build control planes, ledgers, coordinators, or any service where a bad node must not corrupt state, this paper gives you the shape of the whole problem.
What to take away
- PBFT needs at least 3f plus 1 replicas to tolerate f Byzantine faults while preserving a single ordered log.
- The protocol separates normal-case request ordering from view changes, so leader failure does not rewrite committed history.
- Its practicality comes from batching, MACs, checkpoints, and state transfer, not from the agreement proof alone.
Reads with
- The Byzantine Generals Problem
defines the fault model pbft makes practical for replicated services
- Impossibility of Distributed Consensus with One Faulty Process
explains why pbft needs timing assumptions and view changes for liveness
- Bitcoin: A Peer-to-Peer Electronic Cash System
takes byzantine agreement into an open membership setting with very different costs