Viewstamped Replication

Imagine a group of servers that must agree on every operation: which request comes first, which second, and so on forever. If they agree, clients see a single consistent service. If they disagree, chaos reigns — two clients might read different values for the same variable.

Getting servers to agree despite crashes is the distributed consensus problem. In 1988, Barbara Liskov and Brian Shrira solved it in a paper that coined the word viewstamp — years before Paxos became the canonical answer. Their protocol is called Viewstamped Replication (VR).

VR works by designating one server as the primary. The primary sequences every request, ships the operation to backups, waits for a quorum to acknowledge it, and only then replies to the client. If the primary fails, the surviving replicas detect the silence, elect a new primary, and continue — the view change protocol. The key insight is that a quorum overlap guarantees the new primary has seen every committed operation.

Unlike the halting problem, which asks what computers can never do, VR asks what distributed systems can do despite partial failure — and gives a precise, working answer.

Below is a five-replica cluster running Viewstamped Replication. The primary (blue) sequences client requests and the backups (gray) acknowledge them. Click Send request to commit an operation, then click Crash primary to trigger a view change.

<!-- {{c_html_comment}} -->
<div class="vr-wrap">
  <div class="legend">
    <span class="dot primary-dot"></span><span>{{legend_primary}}</span>
    <span class="dot backup-dot"></span><span>{{legend_backup}}</span>
    <span class="dot crashed-dot"></span><span>{{legend_crashed}}</span>
  </div>
  <div id="replicas" class="replicas"></div>
  <div id="log" class="log"></div>
  <div id="status" class="status-bar"></div>
  <div class="btns">
    <button id="btn-request" type="button">{{btn_request}}</button>
    <button id="btn-crash" type="button" class="danger">{{btn_crash}}</button>
    <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
  </div>
  <p class="hint">{{hint_text}}</p>
</div>

/* {{c_css_comment}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.vr-wrap { padding: .5rem; }
.legend { display: flex; align-items: center; gap: .6rem; font-size: .82rem; color: #555; margin-bottom: .6rem; flex-wrap: wrap; }
.dot { display: inline-block; width: 12px; height: 12px; border-radius: 50%; }
.primary-dot { background: #1d6fa8; }
.backup-dot  { background: #7aadcf; }
.crashed-dot { background: #d0d3d8; border: 1px dashed #999; }
.replicas { display: flex; gap: .6rem; flex-wrap: wrap; margin-bottom: .8rem; }
.replica { width: 70px; text-align: center; font-size: .78rem; }
.replica .circle { width: 54px; height: 54px; border-radius: 50%; margin: 0 auto .3rem;
                   display: flex; align-items: center; justify-content: center;
                   font-weight: 700; font-size: 1rem; transition: background .3s; }
.replica.primary .circle { background: #1d6fa8; color: #fff; }
.replica.backup  .circle { background: #7aadcf; color: #fff; }
.replica.crashed .circle { background: #d0d3d8; color: #999; border: 2px dashed #aaa; }
.replica .label  { color: #555; }
.log { background: #f4f6f8; border: 1px solid #dde3ea; border-radius: 8px;
       padding: .5rem .7rem; min-height: 60px; max-height: 130px; overflow-y: auto;
       font-size: .82rem; font-family: ui-monospace, monospace; margin-bottom: .6rem; }
.log-entry { margin: .15rem 0; }
.log-entry.view  { color: #1d6fa8; font-weight: 600; }
.log-entry.op    { color: #296c43; }
.log-entry.crash { color: #c0392b; }
.status-bar { font-size: .95rem; font-weight: 600; min-height: 1.4em;
              margin-bottom: .5rem; color: #1d6fa8; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .6rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.danger { background: #c0392b; border-color: #a93226; }
button.ghost  { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: not-allowed; }
.hint { font-size: .83rem; color: #555; margin: 0; line-height: 1.4; }

// Code not found

Notice the sequence: when the primary crashes, the surviving replicas time out, broadcast a StartViewChange message, collect a quorum of $\lfloor (n-1)/2 \rfloor + 1$ votes, and the replica with the highest view number assumes leadership. The new primary replays any operation that reached a quorum but was not yet confirmed, ensuring no committed work is lost.

VR is solved — Liskov and Shrira (1988) proved it correct, and the 2012 revision pinned down every edge case. Here is what the math says:

• Fault tolerance: to survive $f$ crash failures you need at least $2f + 1$ replicas. Five replicas tolerate two simultaneous crashes; three replicas tolerate one.
• Normal-operation cost: each request costs $O(n)$ messages — the primary sends Prepare to all $n - 1$ backups, waits for $f$ acknowledgements, then sends Commit.
• View-change safety: the new primary collects DoViewChange messages from $f + 1$ replicas. Because any two quorums of size $f + 1$ out of $2f + 1$ overlap in at least one replica, the new primary always sees the most recent committed operation.
• Liveness: as long as the network is eventually synchronous (messages are delivered within some unknown but finite delay), the protocol makes progress.

Crucially, VR only handles crash-stop failures. Servers that lie, send corrupted messages, or act maliciously break its guarantees — for that you need Byzantine fault tolerance, which costs $3f + 1$ replicas and far more messages.

The quorum arithmetic — $\lfloor n/2 \rfloor + 1$ out of $n$ — is the same heart beating inside Paxos, Raft, and every modern consensus library. VR just named it first.

Viewstamped Replication is not a museum piece — its core pattern powers the infrastructure the internet runs on:

• Raft (2014): Diego Ongaro and John Ousterhout designed Raft explicitly to be "as understandable as Paxos is not." Its leader election and log replication are structurally identical to VR's view change and normal operation.
• Apache ZooKeeper / ZAB: ZooKeeper's Atomic Broadcast protocol uses a primary-backup design with a quorum-based leader election — the same quorum overlap that VR pioneered.
• etcd and Kubernetes: etcd stores cluster state for Kubernetes using Raft under the hood. Every time a pod is scheduled, a Raft (VR-derived) quorum commits the decision.
• Google Chubby: Google's distributed lock service uses a Paxos variant, but its design goals — electing a primary, sequencing operations, surviving minority failures — are exactly VR's.
• Replicated databases: CockroachDB, TiKV, and YugabyteDB all replicate data ranges with a consensus layer whose view-change logic echoes VR.

Master the view-change quorum and you understand the halting problem's sibling: not "can a machine solve this?" but "can a group of machines agree despite failures?" — and now you know the answer is yes, with $2f + 1$ replicas and a simple quorum overlap.

Viewstamped Replication answered distributed consensus in 1988 with a single elegant idea: let the replicas elect a new primary when the old one goes silent, and use a quorum overlap to guarantee the new primary has seen every committed operation. Everything else — Paxos, Raft, ZAB — is a variation on that theme.

The $2f + 1$ replica rule is not an arbitrary engineering choice. It is the mathematical minimum that makes two quorums always share a witness, turning a distributed vote into a reliable guarantee. Next time you deploy a three-node etcd cluster, you are running a 36-year-old proof.