PBFT solved Byzantine consensus in 1999, but its view change protocol — the process of switching leaders when the current one fails — costs O(n³) messages. For a 100-node cluster, that's a million messages just to elect a new leader. HotStuff, published in 2019 and now the backbone of Facebook's Diem and several production blockchains, fixed this with a beautifully simple insight.

The core trick: HotStuff replaces PBFT's mesh of all-to-all communication with a star topology centered on the leader. Every phase — Prepare, Pre-Commit, Commit, Decide — follows the same pattern: leader broadcasts a proposal, replicas send signed votes back to the leader, leader aggregates them into a quorum certificate (QC) and broadcasts that. This turns O(n²) per-phase messaging into O(n).

The pipelining insight: Instead of running four separate phases sequentially, HotStuff pipelines them. The QC for phase N of block B becomes the Prepare message for block B+1. A single vote round advances every in-flight block by one phase. Throughput goes up, and the code becomes almost trivial — every phase runs the same logic.

Real-world example: Consider a permissioned blockchain with 100 validators. Under PBFT, a view change during a leader crash requires each replica to send its state to every other replica: 100 × 99 ≈ 10,000 messages per replica, ~1,000,000 total. Under HotStuff, the new leader collects 67 signed NEW-VIEW messages, aggregates them into a QC, and broadcasts once: ~200 messages total. That's a 5,000× reduction. When Diem tested this at 100 nodes across regions, view changes completed in under 2 seconds instead of the 30+ seconds PBFT required.

Rule of thumb: If your Byzantine cluster has more than ~20 nodes and leader failures aren't rare, HotStuff's linear view change is worth the implementation complexity. Below 20 nodes, PBFT's mesh is fine — 20³ = 8,000 messages is nothing.

The threshold signature dependency: HotStuff's O(n) messaging assumes threshold signatures (BLS is the usual choice), where 2f+1 signatures aggregate into a single constant-size proof. Without them, each QC carries 2f+1 individual signatures, and your "linear" protocol becomes O(n²) in bytes. Budget for BLS: sign in ~1ms, aggregate in ~10ms for 100 signers, verify in ~5ms.

The trade-off: HotStuff adds a round of latency compared to PBFT on the happy path (three phases vs two). You pay one extra round trip per decision in exchange for view changes that don't melt your network when a leader dies. For most systems, that's a trivial price.