Introduction

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.

Try It: View Change

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.

<!-- Viewstamped Replication demo: primary-backup cluster with view change -->
<div class="vr-wrap">
  <div class="legend">
    <span class="dot primary-dot"></span><span>Primary</span>
    <span class="dot backup-dot"></span><span>Backup</span>
    <span class="dot crashed-dot"></span><span>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">Send request</button>
    <button id="btn-crash" type="button" class="danger">Crash primary</button>
    <button id="btn-reset" type="button" class="ghost">Reset</button>
  </div>
  <p class="hint">Send a few requests, then crash the primary. The surviving replicas elect a new primary and resume in a higher view number.</p>
</div>

/* Styles for the VR demo */
* { 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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Viewstamped Replication demo: simplified primary-backup with view change.
// N=5 replicas. Quorum = floor((N-1)/2)+1 = 3. Crash-stop failures only.
const N = 5;
// Cluster state: view number, primary index, crashed set, committed ops.
let state = {
  view: 1,
  primary: 0,
  crashed: new Set(),
  ops: [],
  opCounter: 0
};

// Replica display labels
const LABELS = ['R0','R1','R2','R3','R4'];

function quorum(){ return Math.floor((N - 1) / 2) + 1; } // minimum acknowledgers needed

function renderReplicas(){
  const el = document.getElementById('replicas');
  el.innerHTML = '';
  for(let i = 0; i < N; i++){
    const div = document.createElement('div');
    let cls = 'replica ';
    if(state.crashed.has(i)) cls += 'crashed';
    else if(i === state.primary) cls += 'primary';
    else cls += 'backup';
    div.className = cls;
    const circle = document.createElement('div');
    circle.className = 'circle';
    circle.textContent = LABELS[i];
    const lbl = document.createElement('div');
    lbl.className = 'label';
    if(state.crashed.has(i)) lbl.textContent = 'crashed';
    else if(i === state.primary) lbl.textContent = 'primary';
    else lbl.textContent = 'backup';
    div.appendChild(circle);
    div.appendChild(lbl);
    el.appendChild(div);
  }
}

const logEl = document.getElementById('log');
function addLog(msg, cls){
  const e = document.createElement('div');
  e.className = 'log-entry ' + cls;
  e.textContent = msg;
  logEl.appendChild(e);
  logEl.scrollTop = logEl.scrollHeight;
}

function setStatus(msg){ document.getElementById('status').textContent = msg; }

function updateButtons(){
  const alive = N - state.crashed.size;
  document.getElementById('btn-request').disabled = alive < quorum();
  document.getElementById('btn-crash').disabled =
    (alive - 1) < quorum() || state.crashed.has(state.primary) === false && alive - 1 < quorum();
}

function sendRequest(){
  state.opCounter++;
  const op = 'op-' + state.opCounter;
  state.ops.push({ op, view: state.view });
  const acks = N - state.crashed.size - 1; // all non-crashed backups ack
  addLog(
    fmt('Primary sends Prepare %op% (view %view%). Acks received: %acks%/%v%.', { op: op, view: state.view, acks: acks, v: N - 1 }),
    'op'
  );
  if(acks >= quorum() - 1){
    addLog(fmt('Committed %op%.', { op: op }), 'op');
    setStatus(fmt('Committed %op%.', { op: op }));
  }
  renderReplicas();
  updateButtons();
}

function crashPrimary(){
  const old = state.primary;
  state.crashed.add(old);
  addLog(fmt('CRASH: %v%.', { v: LABELS[old] }), 'crash');
  // pick next non-crashed replica as new primary
  let next = (old + 1) % N;
  while(state.crashed.has(next)) next = (next + 1) % N;
  state.view++;
  state.primary = next;
  addLog(
    fmt('View change → view %view%. %v% is new primary.', { view: state.view, v: LABELS[next] }),
    'view'
  );
  // replay any ops committed in the old view to guarantee safety
  const unconfirmed = state.ops.filter(o => o.view === state.view - 1);
  if(unconfirmed.length > 0){
    addLog(fmt('New primary replays %map%.', { map: unconfirmed.map(o => o.op).join(', ') }), 'op');
  }
  setStatus(fmt('View %view%. | Primary: %v%.', { view: state.view, v: LABELS[next] }));
  renderReplicas();
  updateButtons();
}

function resetAll(){
  state = { view: 1, primary: 0, crashed: new Set(), ops: [], opCounter: 0 };
  logEl.innerHTML = '';
  addLog('Cluster initialized. View 1. R0 is primary.', 'view');
  setStatus('Ready. Send a request or crash the primary.');
  renderReplicas();
  updateButtons();
}

document.getElementById('btn-request').addEventListener('click', sendRequest);
document.getElementById('btn-crash').addEventListener('click', crashPrimary);
document.getElementById('btn-reset').addEventListener('click', resetAll);
resetAll();
Result
Console

Notice the sequence: when the primary crashes, the surviving replicas time out, broadcast a StartViewChange message, collect a quorum of ⌊(n−1)/2⌋+1\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.

The Real Complexity

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 ff crash failures you need at least 2f+12f + 1 replicas. Five replicas tolerate two simultaneous crashes; three replicas tolerate one.
  • Normal-operation cost: each request costs O(n)O(n) messages — the primary sends Prepare to all n−1n - 1 backups, waits for ff acknowledgements, then sends Commit.
  • View-change safety: the new primary collects DoViewChange messages from f+1f + 1 replicas. Because any two quorums of size f+1f + 1 out of 2f+12f + 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+13f + 1 replicas and far more messages.

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

Where It Matters

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+12f + 1 replicas and a simple quorum overlap.

Conclusion

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+12f + 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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/viewstamped-replication/Content licensed under CC BY-NC 4.0.