Viewstamped Replication: Consensus Through View Changes

The Problem VR Solves

Imagine a bank ledger replicated across three servers so a single crash never loses a deposit. You need every replica to apply the same operations in the same order — this is state-machine replication. If each replica starts in the same state and deterministically applies an identical sequence of commands, they stay identical forever. The hard part is agreeing on that sequence while machines crash and messages are delayed or reordered.

Viewstamped Replication, introduced by Brian Oki and Barbara Liskov in 1988 and re-presented cleanly as VR Revisited in 2012, provides exactly this. It assumes a crash (fail-stop) model — nodes may halt but never lie — and an asynchronous network that can drop, delay, or duplicate messages but not corrupt them.

• With N = 2f + 1 replicas it tolerates f simultaneous crashes.
• It guarantees linearizability: committed operations appear to execute atomically in some total order consistent with real time.
• It never violates safety, even during network partitions — it only sacrifices liveness, exactly as the CAP theorem and FLP impossibility result require.

How It Works, Step by Step

VR runs three sub-protocols: normal operation, view change, and recovery. Every replica tracks a view-number v, a monotonic op-number, a commit-number, and a log of operations. The primary is chosen deterministically: primary = v mod N.

Normal operation (primary alive):

1. Client -> primary:      REQUEST(op, client-id, request-num)
2. Primary: op-number++, append to log
   Primary -> backups:     PREPARE(v, op, op-number, commit-number)
3. Backup appends in order, replies:
   Backup  -> primary:     PREPAREOK(v, op-number, replica-id)
4. When primary has f PREPAREOKs (a quorum of f+1 incl. itself):
   commit-number = op-number; execute op on state machine
   Primary -> client:      REPLY(v, request-num, result)

View change (primary suspected dead): a backup that times out sends STARTVIEWCHANGE(v+1). On collecting f such messages it sends DOVIEWCHANGE(v+1, log, ...) to the new primary (v+1) mod N. Once that primary receives f+1 DOVIEWCHANGE messages it picks the most up-to-date log among them (largest last-view / op-number), broadcasts STARTVIEW, and resumes. Because any committed op was stored at f+1 replicas, and any DOVIEWCHANGE quorum of f+1 must intersect that set, the new primary is guaranteed to see it.

Complexity and a Worked Trace

Message complexity: normal-case commit is O(N) — one PREPARE fan-out and up to N-1 PREPAREOK replies, though the primary only waits for f of them. Latency: 2 message delays (one round trip) from primary to a quorum. A view change is also O(N) messages (or O(N^2) if STARTVIEWCHANGE is broadcast all-to-all). Space: each replica stores the full operation log, O(number of ops) until a checkpoint truncates it.

Worked trace with N=3, f=1, replicas R0 (primary, v=0), R1, R2:

R0 gets REQUEST(x=5). op-number 1.
R0 -> R1,R2: PREPARE(v=0, x=5, op=1, commit=0)
R1 -> R0: PREPAREOK(0,1,R1)   // f=1 reply is enough
R0: quorum {R0,R1} reached -> commit-number=1, execute, REPLY.
--- R0 crashes ---
R1 times out, sends STARTVIEWCHANGE(v=1) to all.
R2 does likewise. New primary = 1 mod 3 = R1.
R1,R2 send DOVIEWCHANGE(v=1, their logs) to R1.
R1 has f+1=2 logs; both contain op=1 -> op x=5 survives.
R1 -> all: STARTVIEW(v=1, merged log). Service resumes.

The committed op x=5 is never lost because the quorum that committed it (2 nodes) must overlap the quorum that runs the view change (2 nodes) in a 3-node cluster — this quorum-intersection property is VR's safety heart.

Where VR Shows Up in Real Systems

VR's DNA runs through much of modern distributed infrastructure, sometimes explicitly and often by convergent design:

• Harp file system (Liskov et al., 1991) was the original production user of VR, replicating an NFS server for high availability.
• Viewstamped Replication Revisited (Liskov & Cowling, 2012) became a favorite teaching protocol precisely because its view-change mechanism is more concrete and understandable than classic Paxos — MIT's 6.824 and many courses use it.
• TAPIR and Speculative Paxos (Ports et al., UW) build inconsistent-then-reconciled replication directly on VR-style views.
• Raft (2014), the protocol behind etcd (Kubernetes' backing store), Consul, TiKV, and CockroachDB, is essentially VR reframed with a stronger leader and a cleaner log-matching invariant; Ongaro and Ousterhout cite VR as a direct influence.

Anywhere you see a replicated log with a term/view number, an elected leader, and a quorum of f+1, you are looking at a descendant of VR's ideas.

How It Differs From Paxos and Raft

All three protocols solve the same problem with the same 2f+1 quorum math, so the differences are about structure and understandability, not power.

• vs. Multi-Paxos: Paxos treats each log slot as an independent instance of single-decree Paxos and lets slots commit out of order, recovering state by reading back the highest-numbered accepted proposal per slot. VR forbids gaps — backups accept PREPAREs strictly in op-number order — and recovers state wholesale by transferring the freshest log during a view change. The tradeoff: VR is easier to reason about and implement; Paxos is more flexible about concurrency and out-of-order commits.
• vs. Raft: Raft is the closest cousin. Both use a per-leader number (view vs. term) and a contiguous log. Raft adds an explicit leader-election vote and a strong log-matching property that lets a follower reject an inconsistent AppendEntries. VR bakes leader identity into the view number itself (v mod N) rather than voting for arbitrary candidates.

The pithy summary: VR = Paxos made concrete via views; Raft = VR made teachable via explicit elections.

Pitfalls, Failure Modes, and Significance

VR is safe by construction, but implementations stumble in predictable places:

• Byzantine faults are out of scope. VR assumes crash-stop; a lying or corrupted replica breaks it. For adversarial settings you need PBFT or a BFT variant, which requires 3f+1 nodes.
• Liveness during partitions. If fewer than f+1 replicas can communicate, no quorum forms and the system correctly stalls rather than split-brain. Endless view-change storms (dueling primaries) can occur without randomized/backoff timeouts — the same pitfall Raft addresses with randomized election timers.
• Recovery correctness. A restarted replica must not vote or serve using stale in-memory state; VR's recovery protocol makes it fetch a fresh state from the group and only rejoin after learning the current view. Skipping this (or trusting non-durable state) reintroduces lost-write bugs.
• Unbounded logs. Without periodic checkpoints/snapshots the log grows forever; production systems truncate via application-level checkpoints.

Its significance is historical and practical: VR proved, independently and slightly ahead of Paxos, that crash-fault-tolerant consensus was achievable and, crucially, explainable — a lineage that runs straight through Raft into today's cloud control planes.

Viewstamped Replication compared to the other classic crash-fault-tolerant consensus protocols

Property	Viewstamped Replication	Multi-Paxos	Raft
Year / authors	1988 Oki & Liskov (rev. 2012)	1990/1998 Lamport	2014 Ongaro & Ousterhout
Fault tolerance	f crashes, 2f+1 nodes	f crashes, 2f+1 nodes	f crashes, 2f+1 nodes
Leader concept	Primary = view number mod N	Distinguished proposer (leader election external)	Elected leader per term
Recovery of committed ops	Latest log carried via view-change from f+1 quorum	Read-back highest-accepted proposal per slot	Leader with most up-to-date log wins election
Normal-case commit	1 RTT to f+1 quorum	1 RTT (phase 2) after leadership	1 RTT to f+1 quorum
Log divergence allowed	No — backups only accept in-order PREPAREs	Slots can commit out of order	No — AppendEntries enforces contiguity