Practical Byzantine Fault Tolerance (PBFT)
PBFT, published by Miguel Castro and Barbara Liskov in 1999, was the first Byzantine-fault-tolerant agreement protocol fast enough to run real services rather than just exist in theory. It assumes a fixed, known set of n = 3f + 1 replicas and a partially synchronous network — messages eventually arrive, but you cannot bound exactly when. Under those conditions it gives deterministic finality: once a request is committed, it can never be reverted, no probabilistic waiting required.
Each round designates one replica as the primary (leader), and the protocol proceeds in three voting phases. In pre-prepare, the primary proposes an ordering for the next request. In prepare, replicas broadcast that they accept that ordering; collecting 2f + 1 matching prepares (including one's own) proves the network agrees on order. In commit, replicas broadcast that they are ready to finalize, and 2f + 1 matching commits make the request executable and irreversible. The two all-to-all voting phases exist to defeat equivocation by the primary, so honest replicas cannot be split onto conflicting decisions.
If the primary is faulty — silent, or proposing conflicting orders — replicas that time out trigger a view change, rotating to a new primary and carrying forward any request that might already have committed, which preserves safety across leader turnover. The cost is communication: each phase is all-to-all, so message complexity is O(n squared), which is why classical PBFT works for tens to low hundreds of nodes but not for an open network of thousands. Modern blockchain BFT engines such as Tendermint and HotStuff descend directly from PBFT, trimming this overhead and adding stake-based membership.
phase 1 PRE-PREPARE : primary → all (order request m as seq n) phase 2 PREPARE : all → all (collect 2f+1 prepares ⇒ order agreed) phase 3 COMMIT : all → all (collect 2f+1 commits ⇒ m final, execute) # on primary timeout: VIEW-CHANGE → new primary, re-propose uncommitted
Two all-to-all rounds turn a leader's proposal into irreversible agreement among 3f+1 replicas.
PBFT's 2f+1 quorum is what guarantees safety: any two quorums of size 2f+1 in a set of 3f+1 must overlap in at least one honest replica, so they cannot certify two conflicting values.