Tunable consistency and quorums

Masterless distributed architecture (Dynamo model)

In Dynamo-style systems (Amazon's Dynamo, and Cassandra and Riak, which borrow its techniques), there is no single primary. Nodes are peers on a consistent-hashing ring, and any node can coordinate a read or write for any key.

To trade latency, durability and consistency against each other, these systems expose tunable quorum parameters:

• $N$ (replication factor): How many nodes store a copy of each item.
• $W$ (write quorum): How many replicas must acknowledge a write before it succeeds.
• $R$ (read quorum): How many replicas must answer a read.

Each operation waits for its $W$ or $R$ fastest replicas, so its latency is set by the slowest of those. Cassandra exposes the same idea as consistency levels: ONE, QUORUM (a majority, $\lfloor n/2 \rfloor + 1$ of the replicas) and ALL.

---

The quorum condition: $R + W > N$

If

then by the pigeonhole principle any $R$ replicas you read include at least one of the $W$ that acknowledged the latest write, so a read normally sees that write. Vogels calls this strong consistency, but it is not linearizability: Abadi notes that Dynamo-style systems fall short of full consistency even when $R + W > N$ (concurrent writes and sloppy quorums, below, are two reasons).

Common configurations with $N = 3$

---

Conflict resolution and repair

Replicas drift apart (a write missed a replica, a node was down), so these systems repair them:

1. Read repair: During a read, replicas that return stale data are updated with the newer value, repairing them at a convenient moment instead of waiting for background repair.
2. Hinted handoff: If a replica is temporarily unreachable, the write goes to another node along with a "hint"; when the replica returns, the hint is replayed to it. Dynamo combines this with a sloppy quorum: writes go to the first $N$ healthy nodes on the ring, which keeps writes available during failures but means the quorum is not always the "home" replicas.
3. Anti-entropy with Merkle trees: Replicas build hash trees over their key ranges, where each leaf is a hash of a key's value, and compare them; only the branches whose hashes differ need to be synchronized.
4. Last-write-wins vs vector clocks: Cassandra resolves conflicting updates by timestamp (last write wins), so it asks operators to keep clocks synchronized with NTP; clock skew can make the "wrong" write win. Dynamo instead tracks causality with vector clocks and keeps concurrent versions for the application to merge.