5. 1988 versus 2012

The problem: which Viewstamped Replication?

There are two documents called Viewstamped Replication and they do not read alike. Cite "VR" without saying which, and you will confuse people, because the protocol most engineers picture, the clean one with PREPARE, PREPAREOK, COMMIT, a log, and an op-number, is not the one Oki and Liskov published in 1988. That vocabulary is from the 2012 "Revisited" report by Liskov and Cowling. The 1988 paper describes the same core idea in an almost unrecognizably different dress. This chapter reads both on purpose and maps one onto the other, because the difference is not cosmetic and getting it wrong misattributes a 2012 clarification to a 1988 paper.

Why the confusion happens: the 1988 paper is a database paper

The 1988 VR is not presented as state-machine replication. It is presented as a replication method for a distributed transaction system, and it is welded to that setting. The 2012 report names the problem directly: "The original papers explained the protocol as part of a database or file system, which made it difficult to separate the protocol from other details having to do with its use in an application." Reading the 1988 paper, you meet, before you meet the replication protocol itself, atomic transactions, one-copy serializability, strict two-phase locking, two-phase commit with coordinators and participants, tentative versions that become base versions on commit, and nested transactions borrowed from the Argus language. Even Raft's authors flag this in their own paper: "The original description was intertwined with a protocol for distributed transactions, but the core consensus protocol has been separated in a recent update."

The mechanics are dressed differently too. In 1988 the replicas are called cohorts, grouped into a module group; the unit of ordering is a timestamp the primary generates, and the durable record is a communication buffer the primary writes event records into and forces to the backups. The equivalent of "commit this" is force-to, which blocks until a "sub-majority" of backups, one short of a majority, have the events, so that together with the primary a majority holds them. The correctness statement is pure VR under all the transaction vocabulary: "a transaction can commit only if all its events are known to at least a majority of cohorts. The view change algorithm guarantees that events known to a majority of cohorts survive into subsequent views." That is chapter 2 and chapter 4 of this seminar, written in the language of a 1988 transaction system.

Liskov's move, in 2012: strip it to the protocol

The 2012 report's contribution is subtraction. It removes the database, removes two-phase commit, removes locking, and presents what remains: a protocol for replicating an arbitrary deterministic state machine, where clients "run general operations to observe and modify the service state." The transaction machinery is gone because it was never part of the replication idea; it was the application VR was first embedded in. What is left is the clean core this seminar has been describing.

The renaming reflects the reframing. Here is the mapping:

Two differences on that list are more than vocabulary. First, the name itself. VR is named for the viewstamp, and the 2012 report explains the etymology while noting the design changed: "VR as originally defined assigned each operation a viewstamp. A viewstamp is a pair view-number, op-number, with the natural order. At any op-number, VR retained the request with the higher viewstamp. VR got its name from these viewstamps." The 1988 protocol tagged each event with a viewstamp and, during a view change, kept the state of the cohort holding the highest one. The 2012 protocol achieves the same effect with the (v', op-number) comparison in DOVIEWCHANGE from chapter 4, and the viewstamp survives mainly as the name and the reason the comparison orders by view first.

Second, how the new primary is chosen. In 1988 the new primary is the cohort that turns out to hold the most information: "the cohort returning the largest viewstamp is selected as the new primary." In 2012 the primary is fixed in advance by the view number: "the primary is chosen round-robin, starting with replica 1, as the system moves to new views." This is a real design change. The 1988 rule picks whoever is most up to date, which minimizes the log transfer needed; the 2012 rule picks a predetermined replica and then makes it catch up by taking the best log from the DOVIEWCHANGE quorum. The 2012 choice is simpler to reason about, since who leads view v is a pure function of v, and simplicity in the view change is worth a great deal, as the last chapter showed.

There are also honest additions in 2012 that were not in the 1988 paper at all: a full recovery protocol that uses no disk (1988 wrote the view id to stable storage during a view change; 2012 avoids disk entirely, reconstructing state from peers), a reconfiguration protocol that can change the group membership and even the failure threshold f through numbered epochs, and optimizations, witnesses, batching, and checkpoint-based state transfer, several borrowed back from later work on Byzantine fault tolerance. So the 2012 report is not merely a re-explanation; it is an improved protocol. The obligation, when you cite VR, is to say which one you mean.

The modern echo, stated precisely

The two-versions problem is not unique to VR; it is a recurring hazard with foundational protocols, and the same story surrounds Paxos, where the readable modern description arrived long after the cryptic original and the community mostly learned the idea from the later account. The practical lesson for a working engineer is to check the vintage of the protocol you are implementing. If you build "Viewstamped Replication" from a blog post, you are almost certainly building the 2012 protocol, and you should read the 2012 report, because its recovery and reconfiguration protocols are the parts a production system actually needs and the parts the 1988 paper either handled differently or did not cover. The 1988 paper is where the idea was born and where the view-change correctness argument was first made; the 2012 report is the one you deploy.

Principle: A foundational idea often has two texts: the original that invented it inside some application, and the later one that extracts the clean protocol. Cite the right one, and read the later one before you build.