6. VR and its family

The problem: everything looks like VR

Once you know VR, you start seeing it everywhere: a leader ordering a log, a majority acknowledging, a leader-change protocol that preserves committed entries. Raft looks like VR. Multi-Paxos looks like VR. ZooKeeper's Zab looks like VR. The danger is to collapse them all together and declare them the same thing, or to build a family tree with arrows of descent that the history does not support. This chapter sorts the relatives precisely: which converged independently, which descended from which, and where each one genuinely differs. Getting the arrows right matters, because the most famous relationship here, VR and Paxos, is routinely told wrong.

Paxos: the sibling, not the parent

Paxos and VR are the same era and the same shape, and neither came from the other. The 2012 report is unambiguous: "VR was originally developed in the 1980s, at about the same time as Paxos, but without knowledge of that work." Lamport's Paxos, in "The Part-Time Parliament," was written around 1990 and published in 1998; Oki and Liskov's VR was published in 1988. They are contemporaneous and independent, two teams arriving at leader-based, majority-quorum agreement without talking to each other, which is the same pattern of convergence this series keeps finding, and the same signal that the structure is forced by the problem rather than invented by one person.

The 2012 report also draws the real distinction, and it is worth stating precisely rather than saying "VR is Paxos." Paxos is a consensus protocol: it decides one value among proposers. VR is a replication protocol that uses consensus as an ingredient. In the report's words, VR "differs from Paxos in that it is a replication protocol rather than a consensus protocol: it uses consensus, with a protocol very similar to Paxos, as part of supporting a replicated state machine." VR ships the full package, normal-case log replication, view change, recovery, and later reconfiguration, whereas Paxos as originally stated is the consensus core, and turning it into a replicated log, Multi-Paxos, is additional work that the practical systems had to do. Paxos gets its own seminar in this series, so this chapter sets it beside VR without collapsing into it. The relationship was pinned down rigorously much later, by van Renesse, Schiper, and Schneider in "Vive La Différence: Paxos vs. Viewstamped Replication vs. Zab" (2014), which used refinement mappings to show exactly where the three protocols agree and where their differences actually bite. That paper exists because the informal claims, "they are the same algorithm," "they are equivalent," were too loose to be useful.

Raft: the closest modern relative, by design

If you want to see VR alive today, read Raft. Ongaro and Ousterhout's "In Search of an Understandable Consensus Algorithm" (2014) names VR as its nearest kin: Raft "is similar in many ways to existing consensus algorithms (most notably, Oki and Liskov's Viewstamped Replication)." Raft was written to be understandable, and it reaches VR's structure deliberately: a strong leader appends to a replicated log, entries commit on a majority, and a leader election installs a new leader while preserving committed entries. The mapping is nearly one to one. Raft's term is VR's view-number, a monotonically increasing stamp that identifies the current regime and lets stale leaders be detected and ignored. Raft's leader election is VR's view change. Raft's AppendEntries is VR's PREPARE.

The differences are real but narrow. Raft has voters enforce log currency by refusing to vote for a candidate whose log is behind, so the winner already holds every committed entry; VR instead has the new primary pull the most up-to-date log from its DOVIEWCHANGE quorum. Same guarantee, opposite direction of the log comparison. Raft also nailed down details VR left looser, its log-matching property and its membership-change protocol via joint consensus, in the service of being implementable from the paper. And Raft shares with VR the trait that most separates both from classic Paxos: leader election is not an optimization bolted onto consensus, it is part of the protocol, which is what makes both easier to follow than Paxos, where, as the Raft paper notes, leader election is orthogonal to the basic consensus mechanism.

Zab, and the production logs

Zab, the ZooKeeper Atomic Broadcast protocol (Junqueira, Reed, and Serafini, 2011), is the replication protocol under Apache ZooKeeper, the coordination service that half the distributed systems of the 2010s used for leader election and configuration. Zab is another leader-based primary-backup log protocol in the VR family, and it uses epoch numbers where VR uses view numbers. The production replicated logs mostly run on Raft: etcd (the store behind Kubernetes), CockroachDB and TiKV (which run a Raft group per key range), and others. Kafka's KRaft mode manages cluster metadata with a Raft-based quorum, and Kafka's partition leadership carries a leader epoch to fence stale leaders, the same trick as VR's view number. Multi-Paxos underlies Google's Chubby lock service and, extended with real-time clocks, Spanner. Under every one of these is VR's skeleton: a leader imposes a total order on a log, a majority must store an entry before it counts, and a leader-change protocol carries committed entries across via quorum intersection.

The family, at a glance, with what each calls the "view":

• Paxos (Lamport): convergent, independent, contemporaneous; calls the view a ballot or round. The consensus core, which VR uses but is not limited to.
• Raft: the closest modern relative and cites VR; calls the view a term. Strong leader, and election enforces log currency by vote.
• Zab (ZooKeeper): same family, primary-backup broadcast; calls the view an epoch. Powers ZooKeeper coordination.
• Multi-Paxos (Chubby, Spanner): the Paxos line; ballot. A stable leader over many consensus instances.
• etcd, CockroachDB, TiKV: built on Raft; term. Cockroach and TiKV run a Raft group per key range.
• Kafka KRaft: built on Raft with partition epochs; epoch. A metadata quorum plus leader-epoch fencing.

The one relative that is a different problem: Byzantine faults

There is a boundary this family does not cross, and it is important not to blur it. Every protocol above assumes crash faults: a failed replica stops, it does not lie. If replicas can behave arbitrarily, corrupted, compromised, or malicious, sending different messages to different peers, then majority quorums are not enough, because a lying replica can tell one quorum one thing and another quorum something else. Tolerating that is Byzantine fault tolerance, and the practical protocol is PBFT, Castro and Liskov's "Practical Byzantine Fault Tolerance" (1999), which is Liskov again and the direct sequel to this work. PBFT keeps VR's shape, a primary, views, view changes, but pays for lying replicas with larger quorums and an extra message round, and it needs 3f+1 replicas to tolerate f liars rather than VR's 2f+1 for f crashes. The 2012 report notes the lineage in both directions: PBFT "was based on VR," and VR's 2012 optimizations were in turn borrowed back from PBFT. PBFT gets its own seminar in this series. For now the line to hold is clean: VR tolerates crashes, PBFT tolerates lies, and the jump between them is a jump in both the quorum arithmetic and the cost.

Principle: The leader-orders-a-log-and-a-majority-confirms pattern is convergent bedrock, reinvented independently and now under most production systems. Keep the family tree honest: Paxos is a twin not a parent, Raft is the understandable retelling, and Byzantine tolerance is a different and costlier problem, not a bigger quorum.