Quorums and repair

In a leaderless store, a coordinator sends a write to several replicas and waits for enough acknowledgements. Reads also contact several copies. Quorums describe those thresholds, but the numbers are only part of the consistency story.

Read a lagging replica, then increase the read quorum and compare the result.

N, W and R

• N: the number of replicas responsible for a key.
• W: how many must acknowledge a write before it succeeds.
• R: how many responses a read waits for before reconciling versions.

For a fixed replica set, R + W > N means every read set overlaps every successful write set. A read can therefore encounter evidence of a completed write, assuming those replicas retain it and the protocol identifies the right version. It doesn't mean every response is current.

A three-replica example

Take replicas A, B and C, with N = 3, W = 2 and R = 2. Initially all hold version 7. A write of version 8 reaches A and B; C is temporarily unreachable. The coordinator acknowledges after A and B confirm.

This example assumes one sequential writer and a meaningful version order. Returning the first response defeats R = 2; the coordinator must wait and reconcile. Requiring more replicas trades availability and latency for stronger evidence: W = 3 stops writes when any replica is unreachable.

Overlap isn't linearizability

Concurrent writers may produce conflicting versions. A write that times out can still reach some replicas, so later reads may observe it. Without suitable read/write-back rules, one read can see that partial write while a later read misses it. Membership changes, failed replicas and lost durable state complicate the overlap assumption too.

Even W + W > N only establishes overlap between write sets; it doesn't make a replica serialize a read-modify-write operation correctly. A balance or strict quota needs an atomic protocol, such as conditional updates through a leader or a linearizable register implementation, not just quorum arithmetic.

Sloppy quorums and hinted handoff

When normal owners are unavailable, a sloppy quorum may accept acknowledgements from substitute machines. That improves write availability, but a read contacting only normal owners may miss the update despite apparently sufficient R and W.

Hinted handoff stores the update with its intended destination and forwards it after recovery. Hints need retention and delivery monitoring. If the substitute fails or a hint expires before delivery, another repair path must reconcile missing data. Amazon's Dynamo paper describes this availability-oriented design.

Read repair and background repair

When a read finds version 8 on B and version 7 on C, read repair sends the resolved version back to stale replicas. Whether it finishes before returning is a product and implementation choice. Conflicting concurrent versions may require a merge rather than simply picking the largest timestamp.

Unread keys need repair too. Background anti-entropy compares replica contents and transfers differences. Deletion markers must survive long enough for lagging replicas to learn about deletes; dropping them too early can resurrect old values. Monitor repair coverage, not just successful foreground reads.