Introduction

View-Stamped Replication (VSR) was developed by Barbara Liskov and colleagues at MIT in the late 1980s, predating Raft by nearly two decades. The algorithm achieved consensus using a view-based approach where nodes progress through numbered views, with one node serving as the primary in each view.

The name comes from the two key pieces of state that nodes maintain: the view number (indicating their current understanding of who is primary) and the status (whether they are normal, recovering, or have been replaced).

VSR is less well-known than Paxos or Raft, but it influenced both. If you want another angle on consensus algorithms, VSR is worth your time.

Views and Roles

The core abstraction in VSR is the view. A view consists of a view number and an ordered list of replicas. The first replica in the list is the primary, the second is the backup, and so on. Nodes advance through views as failures happen.

stateDiagram-v2
    [*] --> Normal
    Normal --> Normal: Primary receives client requests
    Normal --> Normal: Backup processes prepare messages

    Normal --> ViewChange: Timeout without communication
    ViewChange --> Normal: New view established

    state ViewChange {
        [*] --> StartViewChange
        StartViewChange --> DoViewChange: Received enough VIEW-CHANGE messages
        DoViewChange --> [*]: Sent STARTVIEW to new primary
    }

When a backup detects that the primary is unresponsive (via timeout), it initiates a view change. It increments its local view number and sends VIEW-CHANGE messages to all replicas. Once a node receives VIEW-CHANGE messages from a majority of replicas, it sends a STARTVIEW message to the new primary.

The Normal Phase

In the normal (non-view-change) phase, the primary processes client requests sequentially. When the primary receives a request, it assigns it a monotonically increasing transaction number and forwards an PREPARE message to all backups.

Each backup receives the PREPARE message, persists the operation to its log, and sends an acknowledgment back to the primary. When the primary receives acknowledgments from a majority, it applies the operation to its state machine and responds to the client.

This is similar to how Raft handles log replication, but with a different mechanism for view changes and recovery.

sequenceDiagram
    participant C as Client
    participant P as Primary
    participant B1 as Backup 1
    participant B2 as Backup 2

    C->>P: Request: op(x)
    P->>P: Assign transaction number n=42
    P->>B1: PREPARE(view=5, n=42, op(x))
    P->>B2: PREPARE(view=5, n=42, op(x))
    B1->>P: ACK(view=5, n=42)
    B2->>P: ACK(view=5, n=42)
    P->>P: Apply op(x) to state machine
    P-->>C: Response: OK
    Note over P: Committed: transaction 42

Key points about the normal phase:

1. The primary assigns a monotonically increasing transaction number (not log index like Raft)
2. Operations are forwarded to all backups via PREPARE messages
3. A majority of acknowledgments (including the primary) commits the transaction
4. The primary applies the operation after quorum is reached, not before

Handling Failures and Recovery

VSR handles node failures carefully. When a primary fails, some backup becomes the new primary through the view change protocol. When a failed node recovers, it must rejoin the group and catch up on missed operations.

Recovery involves the recovering node sending a RECOVERY message to the current primary. The primary responds with a STATE message containing the current view number and the operations the recovering node missed. This allows the recovering node to replay those operations and rejoin as a full member.

Relationship to Paxos and Raft

VSR shares conceptual territory with both Paxos and Raft but takes a different path. Like Raft, it has a clear notion of leadership within a view. Like Paxos, it uses quorum-based replication and can tolerate asynchronous communication, within limits.

The view change mechanism is more elaborate than Raft’s leader election. VSR separates “who is primary” from “what is committed,” whereas Raft embeds these in its leader and log replication.

VSR is a solid choice for building replicated state machines, but it is less commonly implemented than Raft. If you need a well-tested consensus algorithm with a mature ecosystem, Raft-based implementations (like etcd) are more readily available.

However, if you’re building a system that requires the specific properties of view-stamped replication, or if you’re working with existing VSR-based code, understanding the algorithm helps.

VSR and Zab: The Direct Lineage

The Zab protocol (ZooKeeper Atomic Broadcast) is essentially VSR adapted for ZooKeeper’s specific needs. Understanding this lineage clarifies why ZooKeeper behaves the way it does.

The key similarities:

• Both use view numbers to track leadership epochs
• Both use a primary-backup model where only the primary can order operations
• Both separate “who is primary” from “what is committed”
• Both use versions of VIEW-CHANGE/STARTVIEW-equivalent messages to transition leadership

The key adaptations Zab made:

Aspect	VSR	Zab
Recovery	Full state replay via STATE messages	Discovery phase + state sync
Epoch concept	View number	Epoch (proposal) number
Commitment	Majority ACK to primary	Quorum of acknowledgments to leader
Abort condition	If a quorum cannot be reached	If quorum is lost, suspend operations

When you debug ZooKeeper leadership issues, the view-change concepts from VSR map directly. ZooKeeper’s zxid (transaction ID) carries the epoch number and transaction counter, much like VSR’s view number plus transaction number.

Comparison to Other Approaches

For more context on consensus in distributed systems, see my posts on CAP Theorem and Consistency Models. These explore the broader landscape of trade-offs in distributed systems.

The Two-Phase Commit post discusses a different coordination approach that is simpler but less fault-tolerant.

VSR vs Raft vs Paxos

Aspect	VSR	Raft	Paxos
Leader Concept	Primary within view	Single strong leader	Optional distinguished proposer
Reconfiguration	View changes with majority	Joint consensus	Complex, requires extra care
Recovery Complexity	RECOVERY/STATE messages	Log truncation + snapshot	Depends on implementation
Commitment	Majority of acknowledgments	Majority of AppendEntries	Majority of Accept messages
Log Structure	Transaction numbers	Log indices with terms	Proposal numbers
Node State	View number + status	Current term + votedFor	Promised proposal numbers

Aspect	VSR	Raft	Paxos
Understandability	Moderate	High (designed for clarity)	Low (proof-heavy)
Performance	Comparable to Raft	Optimized for throughput	Lower due to 2 phases
Influence	CORFU, Zab	etcd, CockroachDB, TiKV	Chubby, Spanner
Formal Proof	Yes	Yes	Yes (classical)
Year Published	1988	2014	1998 (first paper)

Membership Changes and Reconfiguration

VSR handles cluster membership changes through the view change mechanism. When nodes need to be added or removed, the system progresses through a new view that includes the updated membership configuration.

The reconfiguration procedure follows these steps:

sequenceDiagram
    participant O as Old Configuration
    participant L as Leader
    participant N as New Node
    participant F as Followers

    Note over O,L: Client requests configuration change
    L->>L: Prepare reconfiguration view v+1
    L->>N: STARTVIEW(v+1, new_config)
    L->>F: STARTVIEW(v+1, new_config)
    Note over N: New node catches up via STATE messages
    N-->>L: ACK(v+1)
    F-->>L: ACK(v+1)
    Note over L: Quorum reached in view v+1
    Note over L,N,F: New configuration active

Key points about VSR reconfiguration:

1. View-based approach — Membership changes are embedded in view changes, giving a natural mechanism for transitioning between configurations
2. Catch-up via STATE messages — New nodes receive the current state from the primary before participating in consensus
3. No joint consensus required — Unlike Raft’s two-phase joint consensus, VSR transitions in a single view change once the new node catches up
4. Transition safety — Quorum requirements prevent two conflicting configurations from operating simultaneously

The primary sends STATE messages containing the view number, committed transaction number, and the recent log entries the new node needs to replay. Once the new node acknowledges receipt and catches up, it becomes a full voting member.

Recovery and Checkpointing Procedure

VSR nodes can fail and recover, requiring them to rejoin the cluster with the correct state. The recovery procedure uses the RECOVERY and STATE message exchange.

sequenceDiagram
    participant R as Recovering Node
    participant P as Primary
    participant B as Backup

    R->>P: RECOVERY(v=5, n_recovered)
    Note over P: Current view = 5, committed_n = 100
    P->>R: STATE(view=5, committed=100, operations=[...])
    Note over R: Replay operations 1-100
    R->>R: State machine up-to-date
    Note over R: Rejoin as full member

The recovery procedure:

1. RECOVERY message — The recovering node sends its last known view number and last recovered transaction number to the current primary
2. STATE response — The primary responds with the current view, the highest committed transaction number, and any uncommitted operations the recovering node missed
3. State reconstruction — The recovering node replays the missing operations to its state machine, bringing it back up to date
4. Return to service — Once caught up, the node resumes normal operation and can participate in quorum decisions

Checkpointing in VSR

Checkpointing (snapshotting) in VSR serves the same purpose as in Raft: bounding log growth for long-running clusters. The checkpoint contains:

class Checkpoint:
    def __init__(self, view_number, last_transaction, state):
        self.view_number = view_number
        self.last_transaction = last_transaction  # Last committed transaction
        self.state = state                        # State machine state snapshot
        self.checksum = compute_hash(state)       # Integrity verification

Checkpoint creation:

• The primary periodically creates checkpoints of the application state machine
• Checkpoints are triggered based on transaction count thresholds (e.g., every 10,000 transactions)
• Log entries up to the checkpoint’s last_transaction can be discarded

Checkpoint recovery:

• A recovering node receives the latest checkpoint via STATE message
• The checkpoint includes enough information to replay from that point
• Nodes verify checkpoint integrity via the embedded checksum

This approach means:

• Memory usage stays bounded even with high transaction rates
• Recovery time stays bounded by the checkpoint interval, not total transaction history
• Network transfer during recovery stays proportional to checkpoint size, not full history

Production Failure Scenarios

Network Partition During View Change

A network partition during a view change can leave two nodes both thinking they are primary. VSR prevents split-brain through its quorum requirement for establishing any new view.

Here is how the race condition works. Suppose primary P is on side A of the partition, and backup B on side B times out on P and triggers a view change. B increments its local view number and broadcasts VIEW-CHANGE messages to all replicas. If B can reach a majority, it collects enough VIEW-CHANGE messages to form a quorum. It then sends a STARTVIEW to whichever node it believes should be the new primary, which could be itself or another backup that sent the highest view number.

The node that receives the STARTVIEW becomes the legitimate primary. It starts accepting and ordering client requests. P on side A of the partition cannot receive VIEW-CHANGE messages from any majority. It may keep receiving client requests, but it cannot commit them because it cannot gather acknowledgments from a quorum of backups. It stalls.

What stops false commits is the quorum overlap property. Any two successive views that both reach quorum must share at least one node that voted in both. This means at most one configuration of nodes can certify a new primary at any given view number. A partitioned node trying to act as primary will fail to gather quorum acknowledgments and cannot drive transactions to commit.

Client requests sent to the partitioned primary will eventually time out. Clients should retry against the new primary once they detect the timeout, using their original transaction number if known. The new primary must deduplicate based on client ID and transaction number to avoid double-applying operations.

The partition is detected through timeout on the backup side. The backup does not need to know whether the primary is truly dead or just unreachable—it treats silence as failure and initiates the view change protocol. This means VSR tolerates asynchronous networks as long as messages are eventually delivered and the timeout is set appropriately.

Cascading Node Failures

When multiple nodes fail in quick succession, VSR can reach a state where no majority of nodes remains reachable. The cluster becomes unavailable for writes—a deliberate trade-off that favors correctness over availability.

The failure threshold depends on cluster size. In a 5-node cluster, any 2 nodes can fail and the remaining 3 still form a majority. In a 3-node cluster, a single failure leaves only 2 nodes, which is still a majority. But if a second node fails before the first recovers, the cluster is left with 1 node—below majority—and cannot make progress.

VSR has no automatic recovery path when a majority cannot be formed. The algorithm waits for one of the failed nodes to recover and rejoin. Once a recovering node completes its STATE synchronization with the current primary and rejoins the cluster, a majority can be re-established and normal operation resumes.

During the unavailable period, client requests are rejected or time out. There is no speculative or degraded mode that allows partial writes. This is the same safety trade-off Raft and Paxos make: if you cannot confirm that a majority of nodes have acknowledged an operation, you cannot safely commit it.

The vulnerability window for cascading failures depends on detection time. Longer view-change timeouts keep a failed primary appearing alive to its backups. Setting timeouts too short causes spurious view changes during temporary load spikes. Setting them too long delays failure detection. Most production deployments use heartbeat intervals in the 100ms to 1s range with a few missed heartbeats before triggering a view change.

Administrators should track the number of nodes in each view and alert when cluster size drops below the majority threshold. Some implementations add a witness or observer node type that participates in view changes without storing data, which reduces the failure threshold without adding replication overhead.

Checkpoint Corruption

A recovering node that gets a corrupted checkpoint from the primary risks replaying incorrect state to its state machine. VSR handles this with a checksum embedded in each checkpoint. The receiving node verifies integrity before applying anything to its local state.

When a node initiates recovery, it asks the current primary for the latest checkpoint via the RECOVERY message exchange. The primary responds with a STATE message containing the checkpoint object, which includes the view number at the time of the checkpoint, the last committed transaction number, a serialized snapshot of the application state, and a checksum computed over the state data. The recovering node recomputes the checksum over the received state and compares it against the embedded value. A mismatch means something went wrong.

On detecting corruption, the recovering node has two options. It can ask for the checkpoint again from the primary, in case the error happened during network transmission. Or it can ask a different replica that was part of the majority in the view where the checkpoint was created. If all replicas return corrupted checkpoints, the node cannot recover through VSR alone and needs administrative intervention—potentially restoring from an external backup or rebuilding the state from the transaction log if enough replicas are available.

The checksum does not tell you whether the corruption is partial (some bytes flipped) or complete (checkpoint truncated). Both cases trigger the same recovery path. This is why VSR implementations tend to use cryptographic hashes like SHA-256 rather than simpler checksums that might miss certain error patterns.

Checkpoint corruption during normal operation is not a concern in VSR’s design. Checkpoints are created by the primary and only transferred to recovering nodes. If the primary’s checkpoint becomes corrupted, clients or other replicas might eventually detect the corrupted state in normal operation, but VSR does not give the primary a way to verify its own checkpoint. Production deployments usually pair checkpoint integrity checks with external monitoring and periodic health checks on the primary’s state.

View Number Overflow

View numbers in VSR are stored as integers, and theoretically they can overflow if a cluster runs long enough with frequent view changes. For most deployments this is not a realistic concern, but the mechanism is worth knowing.

VSR view numbers typically use 64-bit integers. Even with a view change every second, a 64-bit counter would not overflow for hundreds of millions of years. Most deployments use 32-bit or 64-bit integers without special overflow protection, relying on the practical infeasibility of overflow rather than explicit defenses.

The overflow concern ties into the reconfiguration mechanism. When an administrator wants to reset view numbers as a precaution or because they are approaching a practical limit, they perform a reconfiguration that effectively starts fresh. The reconfiguration creates a new view with the updated membership configuration, and the new view’s number can be set to any value the administrator chooses, as long as it is higher than any view number existing nodes have seen. This gives administrators a controlled way to reset the counter without disrupting the cluster.

For long-running deployments that expect extremely high view change rates, some VSR-inspired systems add explicit overflow guards. These usually take the form of alerts when the view number exceeds a configurable threshold, such as 90% of the maximum value for the integer type, giving administrators advance notice to plan a reconfiguration.

A more practical concern than overflow is view number synchronization after a reconfiguration. When a new node joins or an existing node recovers, it receives the current view number via the STATE message. If the recovering node has a stale view number that is too far behind, the primary may need to send a large number of missed operations. This is bounded by the checkpoint interval. If checkpoints are created every 10,000 transactions, the recovery gap is at most the checkpoint interval regardless of how long the node was down.

Quick Recap Checklist

Before diving deeper, here are the key points to remember about View-Stamped Replication:

• VSR uses views—a view number plus an ordered replica list—to track leadership
• The first replica in a view is the primary; remaining replicas are backups
• Transaction numbers (not log indices) identify operations in the order they are committed
• A majority of acknowledgments commits a transaction; the primary applies it after quorum
• View changes happen when a backup detects an unresponsive primary via timeout
• A quorum of VIEW-CHANGE messages promotes a new primary in a higher-numbered view
• Recovery uses RECOVERY/STATE message exchange to replay missed operations
• Checkpointing bounds log growth and speeds up recovery for long-running clusters
• Reconfiguration embeds membership changes in view changes—no joint consensus needed
• VSR influenced CORFU, ZooKeeper’s Zab, and shares concepts with Raft and Paxos

Interview Questions

Further Reading

• Barbara Liskov’s Original VSR Paper (1988) — The original paper introducing View-Stamped Replication
• Zab Protocol Specification — ZooKeeper’s Zab protocol and its relationship to VSR
• CORFU Protocol — Distributed shared log storage inspired by VSR
• Raft Paper (2014) — Compare VSR’s view-based approach with Raft’s leader-based consensus
• Ongaro and Ousterhout’s Raft PhD Thesis — Includes discussion of VSR and Paxos influences on Raft

Conclusion

View-Stamped Replication is a consensus algorithm worth knowing about. It predates Raft, influenced both Paxos and Raft, and provides a coherent approach to achieving consensus through views and quorum-based replication.

If you’re interested in the history and diversity of consensus algorithms, VSR is worth studying. It shows that there are many valid approaches to the same fundamental problem.