Reaching consensus among processes that may lie is a problem with sharp boundaries. Fischer, Lynch, and Paterson proved that no deterministic protocol can guarantee consensus in a fully asynchronous system if even one process may crash. Synchronous models avoid this result, but they assume bounds on message delay that real networks routinely violate. The practical question is which model is weak enough to be realistic yet strong enough to admit a solution.

Dwork, Lynch, and Stockmeyer answered this in 1988 with partial synchrony. In this model the network may behave arbitrarily until an unknown Global Stabilisation Time (GST), after which messages arrive within a bound Δ. Protocols in this model separate their obligations cleanly. Safety, meaning no two correct replicas decide differently, must hold in every execution. Liveness, meaning every correct replica eventually decides, need only hold after GST. With n ≥ 3f + 1 replicas, any two quorums of 2f + 1 intersect in at least f + 1 replicas. That intersection guarantees at least one honest witness in common, and nearly every safety proof in this field reduces to it.

Researchers have explored the design space within this model for more than two decades, and three developments define the modern landscape. PBFT established that Byzantine replication could be practical. HotStuff reduced per-view communication to linear complexity. Optimistic protocols accelerate the fault-free path without weakening the guarantees that matter when things go wrong. Each repositions costs within the same formal structure, and examining where those costs land shows what is fundamental and what is engineering.

Castro and Liskov's Practical Byzantine Fault Tolerance (1999) organises replicas into a sequence of views, each with a designated primary. In the normal case, the primary assigns a sequence number to a client request and broadcasts a PRE-PREPARE message. Replicas that accept it broadcast PREPARE. Once a replica holds the pre-prepare and 2f matching prepares from distinct replicas, the request is prepared. Replicas then broadcast COMMIT. A request with 2f + 1 matching commits is committed locally and executed in sequence order.

The two all-to-all phases serve distinct purposes. The prepare phase guarantees ordering within a view. Two prepared certificates for different requests at the same view and sequence number would require two quorums that intersect in an honest replica that voted twice, which is impossible. The commit phase guarantees ordering across views. A committed request is prepared at f + 1 or more honest replicas, so it is guaranteed to survive into any future view.

Ensuring that survival is the job of the view change protocol, the intellectual core of PBFT. When replicas suspect the primary, typically through a timeout, they broadcast VIEW-CHANGE messages. These carry each replica's last stable checkpoint and the prepared certificates it holds beyond that checkpoint. The new primary collects 2f + 1 such messages and broadcasts NEW-VIEW. This message re-proposes every request that appears prepared in the collected set and fills any gaps with null requests. Quorum intersection guarantees that every committed request appears in at least one collected certificate.

The cost of this design shows up in message complexity. Each normal-case phase is all-to-all, which yields O(n²) messages per request. The view change is more expensive still. With signed certificates, each VIEW-CHANGE message carries O(n) authenticators. The NEW-VIEW message embeds 2f + 1 of them, so broadcasting it to all replicas moves O(n³) authenticators. Checkpoints and watermarks bound the log and enable garbage collection, but they do not change this asymptotic profile.

Liveness depends on timeouts that double after each failed view change. After GST, timeouts eventually exceed actual delays, and an honest primary completes a view. PBFT therefore exhibits the canonical structure of partially synchronous protocols. Its safety is unconditional and proven through quorum intersection. Its progress depends on timing assumptions that need only hold eventually. At small n the quadratic normal case is affordable, which is why PBFT remained the reference design for a decade.

Takeaway

In PBFT, the commit phase exists to protect future views rather than the current one. The hardest obligation in any consensus protocol is honouring decisions on behalf of leaders who have not yet been elected.

As Byzantine replication moved into settings with hundreds of replicas, quadratic communication became the binding constraint. HotStuff, introduced by Yin, Malkhi, Reiter, Gueta, and Abraham in 2019, restructures the protocol around a star topology. Replicas send their votes only to the leader. The leader aggregates n − f votes into a quorum certificate (QC) and broadcasts it. With threshold signatures a QC has constant size, so each phase costs O(n) authenticators.

The more significant contribution is a linear view change. In PBFT, the new primary must forward evidence about every prepared request so that replicas can verify its proposal. In HotStuff, each replica maintains a locked QC and sends only its highest QC to the new leader, which extends the highest QC it receives. A replica votes for a proposal under either of two conditions. The first is that the proposal extends the replica's locked branch. The second is that the proposal's justifying QC carries a higher view than the lock. This second condition is the liveness rule that allows an honest leader to unlock replicas safely.

This simplification costs an extra phase. HotStuff runs prepare, pre-commit, and commit phases before a decision, one more than PBFT. The reason is subtle. Two-phase protocols such as Tendermint achieve a linear view change only because the new leader waits a known Δ to be sure it has observed the highest lock. With three phases, the protocol guarantees that if any honest replica is locked, then at least f + 1 honest replicas already hold a QC of equal rank. Any n − f new-view messages must therefore include one of them. This property yields optimistic responsiveness: after GST, an honest leader makes progress at actual network speed rather than at the worst-case bound.

Because the phases share a uniform structure, they can be pipelined, a variant known as chained HotStuff. Each block's QC serves three roles at once. It is the prepare QC for the block's own proposal, the pre-commit QC for its parent, and the commit QC for its grandparent. A block commits once a three-chain of consecutive QCs forms. Throughput approaches one decision per view, and leader rotation becomes nearly free, which improves fairness and censorship resistance.

Linearity has precise limits. The Dolev–Reischuk lower bound establishes that deterministic Byzantine agreement requires quadratic communication in the worst case. HotStuff's claim is narrower: communication is linear per view after GST when the leader is honest. A cascade of f faulty leaders still costs O(fn) in total. Later protocols, including Jolteon and Fast-HotStuff, deliberately return to a quadratic view change in order to recover two-phase latency in the common case. These choices show that the trade-off remains an open design dimension rather than a settled question.

Takeaway

HotStuff purchases linear complexity with one extra round of latency. Asymptotic gains in consensus are rarely free; they are usually moved to another part of the protocol.

Deployed systems show that faults are rare. Most views have honest leaders, timely networks, and fully responsive replicas. Optimistic protocols exploit this by defining a fast path that decides in fewer rounds when conditions are favourable, alongside a slow path that preserves safety otherwise. The central design challenge is that the two paths must compose correctly. Any value decided on the fast path must be recoverable by the slow path's view change.

Zyzzyva, published by Kotla and colleagues in 2007, pushed this idea close to its limit. Replicas execute requests speculatively as soon as they receive the primary's ordering, and they reply directly to the client. If the client receives 3f + 1 matching responses, the request completes in three message delays. If it receives only 2f + 1, the client assembles a commit certificate and distributes it, falling back to a two-phase path. In this design, clients rather than replicas detect divergence and trigger its correction.

Zyzzyva also illustrates the hazard of this approach. In 2017, Abraham, Gueta, Malkhi, Alvisi, Kotla, and Martin showed that its view change could violate safety. Under a specific sequence of view changes, a request completed on the fast path could be lost. The flaw sat exactly at the boundary between the two paths, where informal reasoning is weakest. The episode is a strong argument for mechanically checked specifications of the kind that TLA+ and Ivy make tractable.

Fast paths also carry resilience costs that can be calculated exactly. Martin and Alvisi's FaB Paxos decides in two communication steps but requires n ≥ 5f + 1. Later analysis tightened this bound to 5f − 1. The underlying reasoning is quorum arithmetic. A value decided by a fast quorum must remain uniquely identifiable within any view-change quorum, even after Byzantine replicas equivocate and some honest replicas fall silent. Each extra round saved in the common case must be paid for with additional replicas.

SBFT, by Gueta and colleagues in 2019, takes a more measured approach. It sets n = 3f + 2c + 1, which tolerates c slow or crashed replicas without abandoning the fast path. It also uses collectors and threshold signatures, and it falls back to a linear PBFT-style path when needed. A more general lesson comes from the Abstract framework of Guerraoui and colleagues. Fast and slow modes can be treated as separately verified modules, connected by a switching protocol whose safety is proven on its own.

Takeaway

An optimistic path is only as safe as the handover that follows it. The proof obligation lies at the seam between the fast and slow paths, not inside either one.

Taken together, these protocols reveal a stable formal structure beneath their apparent variety. Safety rests on quorum intersection among n ≥ 3f + 1 replicas. Liveness rests on eventual synchrony and a mechanism for replacing faulty leaders. Every innovation since PBFT has moved costs around within this structure rather than escaping it.

PBFT pays quadratic communication for a simple, auditable view change. HotStuff pays a round of latency for linearity and responsiveness. Optimistic protocols pay in resilience or proof complexity for faster common-case decisions. Lower bounds such as Dolev–Reischuk and the fast-path resilience thresholds mark where these trade-offs become hard limits.

For the architect, the guiding principle is to locate each guarantee precisely. Some properties hold unconditionally, some depend on GST, and some depend on optimism. The view change is where these categories meet, so it is where specification and verification effort yields the greatest return.