A protocol built on views
Viewstamped Replication, or VR, is a consensus protocol predating Paxos popularity that keeps a replicated state machine consistent through crashes. Replicas operate in numbered views, and each view has one primary that orders client requests.
Normal operation
In a stable view the primary assigns each request an op number and broadcasts a prepare to backups.
- Backups append the request and reply prepareok.
- After a majority of prepareoks, the primary commits and replies to the client.
- Backups learn the commit point from later messages and apply requests in op number order.
View change
If backups suspect the primary has failed, they start a view change to the next view. The new primary collects logs from a majority, picks the most up to date one, and resumes normal operation. Because a majority is consulted, every committed request appears in the recovered log, so nothing acknowledged to a client is lost.
VR also defines a recovery protocol so a restarted replica safely rejoins by learning current state from a quorum.
Key idea
Viewstamped Replication orders requests through a per view primary and uses view changes plus majority log recovery to preserve every committed request.