The encyclopedia · R&D & Science · Technical decision · 1999
PBFT made Byzantine-fault-tolerant replication fast enough for real use
Castro and Liskov's protocol lets a replicated service survive arbitrary faults with 3f+1 nodes, in asynchronous networks, at practical speed.
Massachusetts Institute of Technology
The solution
By 1999, distributed systems could tolerate crashes but not Byzantine faults — nodes that lie, forge or behave arbitrarily. Earlier BFT schemes were either theoretical, too slow, or assumed synchrony, which attackers could break by delaying honest nodes.
Miguel Castro and Barbara Liskov's 'Practical Byzantine Fault Tolerance' showed replication could survive f Byzantine failures with 3f+1 replicas in asynchronous networks like the Internet. A three-phase protocol orders requests, and clients wait for f+1 identical replies before trusting a result.
The arithmetic is the mechanism: any two sets of 2f+1 replicas intersect in at least one correct node, so conflicting outcomes cannot both gain enough support. The authors built a Byzantine-fault-tolerant NFS and measured overhead an order of magnitude below earlier protocols.
Why it worked
- Two 2f+1 quorums always share an honest replica
- Three phases bind a request's ordering across replicas
- Safety avoids timing assumptions, only liveness needs them
- The NFS implementation proved real-world speed
What can be applied
When failures can be malicious, size redundancy so honest quorums must intersect: with 3f+1 replicas, any two 2f+1 majorities share a correct node. Correctness follows from counting, not trust.
Aftermath
PBFT became the standard reference for practical Byzantine fault tolerance and the foundation for later BFT consensus designs, including distributed ledgers that combine Byzantine agreement with blockchain-style replication.
Sources
spotted an error? The archive wants to know.