On this page

Quorums & Leaderless Replication

Keeping several copies of data in sync is the central problem of replication. The Replication page surveys the three classic strategies — single-leader, multi-leader and leaderless — and Database Replication shows how PostgreSQL and MySQL do the single-leader kind in production. This page goes deep on the strategy that gives up having a leader at all, and on the tool that makes it work: the quorum.

The idea is disarmingly simple. Store each value on N replicas. Count a write as successful once W of them confirm it. When reading, ask R of them and take the newest answer. If W + R > N, the replicas you read from must include at least one that saw the latest successful write.

That one inequality buys a lot: no leader to elect, no failover, writes that keep working while some replicas are down, and latency set by the fastest replicas rather than the slowest. But the inequality also promises much less than people think. It does not give you linearizability. It says nothing about concurrent writes. It is weakened by sloppy quorums and can be silently broken by a failed write, a clock skew or a disk restore. This page covers both halves: the mechanics that make leaderless replication work, and the edge cases that make it subtle.

We will cover:

  1. The replication algorithm families, and where each fits
  2. Quorum mechanics — N, W, R — with worked examples for N = 3 and N = 5
  3. Quorum intersection math, including staleness probabilities
  4. What quorums do not guarantee (and why they are not linearizable)
  5. Sloppy quorums and hinted handoff
  6. Read repair
  7. Anti-entropy with Merkle trees, with a worked example
  8. Conflict resolution: last-write-wins vs siblings
  9. Tunable consistency in Cassandra, Riak and DynamoDB
  10. Session guarantees and the edge cases that bite in production

1. Replication Algorithm Families

Before zooming in on leaderless replication, it helps to see where it sits. There are four broad families of replication algorithm, distinguished by who accepts writes and how they propagate.

flowchart TB
    subgraph PB["Primary-backup"]
        C1["Client"] --> P["Primary"]
        P --> B1["Backup"]
        P --> B2["Backup"]
    end
    subgraph MP["Multi-primary"]
        C2["Client"] --> P1["Primary (region A)"]
        C3["Client"] --> P2["Primary (region B)"]
        P1 <--> P2
    end
    subgraph CH["Chain replication"]
        C4["Writer"] --> H["Head"] --> M["Middle"] --> T["Tail"]
        T -->|"reads + acks"| C5["Reader"]
    end
    subgraph LL["Leaderless"]
        C6["Client / coordinator"] --> R1["Replica 1"]
        C6 --> R2["Replica 2"]
        C6 --> R3["Replica 3"]
    end

1.1 Primary-backup (single-leader)

One replica, the primary, orders all writes and ships them to backups (followers), synchronously or asynchronously. Reads can go to the primary (fresh) or to backups (possibly stale).

  • Strength: a single total order of writes, so no write conflicts. Easy to reason about.
  • Weakness: the primary is a bottleneck and a single point of failure; failover is the hard part. Choosing a new primary safely requires something like consensus — otherwise you risk split brain.
  • Fits: most relational databases, most systems where a total order of writes matters.

When the primary election and the log replication are both done with a consensus protocol, primary-backup becomes a replicated state machine — see Replicated State Machines.

1.2 Multi-primary (multi-leader)

Several replicas accept writes independently — typically one per region or per device — and exchange changes asynchronously.

  • Strength: local write latency in every region; each region keeps working during an inter-region partition.
  • Weakness: concurrent writes to the same data in different regions conflict, and something must resolve them.
  • Fits: multi-region deployments with mostly region-local writes, offline-first clients, collaborative editing (often with CRDTs).

1.3 Chain replication

Proposed by van Renesse and Schneider (2004). Replicas form a chain. Writes enter at the head and are forwarded node by node; a write is committed when it reaches the tail, which acknowledges it. Reads are served by the tail.

  • Strength: strong consistency (linearizable reads from the tail) with high write throughput, because each node sends each update once. Recovery is simple — a failed node is spliced out of the chain.
  • Weakness: write latency grows with chain length; the tail serves all reads (CRAQ, a later variant, lets any node serve reads of objects that have no uncommitted writes in flight). A separate configuration service (often consensus-based) must manage chain membership.
  • Fits: storage systems inside one datacenter that want strong consistency and high throughput, such as object stores and some research key-value stores.

1.4 Leaderless

Any replica can accept a write. Clients (or a coordinator node acting on their behalf) send each write to all N replicas and each read to several, and use quorums and versions to decide what is current. This is the design of Amazon's Dynamo (2007 paper), and of the systems it inspired: Riak, Cassandra and Voldemort.

  • Strength: no leader election and no failover; writes succeed as long as W replicas are reachable; tolerant of slow nodes because only the fastest W or R responses matter.
  • Weakness: concurrent writes to the same key can conflict; no single order of writes; consistency is subtle.
  • Fits: high-availability key-value workloads that can tolerate (or explicitly resolve) concurrent updates — shopping carts, session data, time series, user activity, telemetry.

1.5 Choosing a family

Primary-backupMulti-primaryChainLeaderless
Who accepts writesOne primaryOne per region/siteHead onlyAny replica
Write conflictsNoneYesNoneYes
Read consistencyFresh at primary, stale at backupsStale across sitesLinearizable at tailTunable
Failover neededYes (hard)Per siteReconfigurationNo
Behaviour under partitionMinority side cannot writeAll sides writeChain stalls until reconfiguredWrites continue while W reachable
Latency shaped byPrimary (+ sync backups)Local siteChain lengthFastest W / R replicas
Typical systemsPostgreSQL, MySQL, MongoDB replica setsMulti-region MySQL/Postgres setups, CouchDBCRAQ, some object storesDynamo, Riak, Cassandra

2. Quorum Mechanics

2.1 The three numbers

  • N — the replication factor: how many replicas store each key. Usually 3, sometimes 5. In Dynamo-style systems N applies per key, and the N replicas are chosen by walking the consistent hashing ring clockwise from the key's position (the preference list).
  • W — the write quorum: how many replicas must acknowledge a write before it is reported successful.
  • R — the read quorum: how many replicas must respond to a read before a result is returned.

A write is always sent to all N replicas. W only controls how many acknowledgements the client waits for. Likewise a read is typically sent to R replicas (some systems send it to all N and wait for R).

sequenceDiagram
    participant C as Coordinator
    participant A as Replica A
    participant B as Replica B
    participant D as Replica C
    Note over C,D: N=3, W=2, R=2
    C->>A: put(k, v2, version 2)
    C->>B: put(k, v2, version 2)
    C->>D: put(k, v2, version 2)
    A-->>C: ack
    B-->>C: ack
    Note over C: 2 acks = W, report success to client
    D-->>C: ack (arrives late, ignored for latency)
    C->>B: get(k)
    C->>D: get(k)
    B-->>C: v2 @ version 2
    D-->>C: v2 @ version 2
    Note over C: 2 replies = R, return the highest version

2.2 The intersection rule

If W + R > N, every read quorum overlaps every write quorum in at least one replica. So a read that starts after a write has completed will contact at least one replica holding that write — and if versions are comparable, the coordinator can pick it out as the newest.

A second, separate rule matters for writes:

  • If W > N/2, any two write quorums overlap. This prevents two writes from both succeeding on completely disjoint sets of replicas, which matters if you want writes to be ordered by version numbers assigned at the replicas.

2.3 Worked example: N = 3

WRW + R > N?Writes tolerate downReads tolerate downCharacter
11No (2 ≤ 3)22Fastest, most available; reads frequently stale right after writes
21No (3 ≤ 3)12Durable writes, but a read can miss them
12No (3 ≤ 3)21Read can miss a write on a single replica
22Yes11The standard "quorum/quorum" setting
31Yes02Read-optimised: any one replica has every completed write, but any replica down blocks writes
13Yes20Write-optimised: any replica down blocks reads
33Yes00No fault tolerance at all — never useful

"Writes tolerate down" is N − W: how many replicas can be unavailable while writes still succeed. "Reads tolerate down" is N − R.

Concretely for W = 2, R = 2: replica C is down. A write to A and B succeeds (2 acks). A read from A and C — C is down, so the coordinator also tries B and gets 2 replies from A and B. Both have the write. Now suppose instead the read happens to contact B and C after C recovers but before C has caught up: B has the write, C does not. The overlap (B) carries the new version and the coordinator returns it.

2.4 Worked example: N = 5

WRW + R > N?Writes tolerate downReads tolerate downNotes
33Yes22Majority/majority — symmetric, common choice for N=5
42Yes13Cheaper reads
24Yes31Cheaper writes, but W ≤ N/2 means two writes can land on disjoint replicas
51Yes04"Write all, read one"
22No33Fast, but stale reads likely

N = 5 with W = R = 3 tolerates two failed replicas for both reads and writes, which is why it appears in deployments that must survive one replica being down for maintenance and another failing unexpectedly.

2.5 Latency: quorums are a tail-latency tool

A quorum operation completes when the W-th (or R-th) fastest replica responds. If replica latencies are independent, waiting for the 2nd fastest of 3 is far better than waiting for the slowest.

Illustrative example: suppose each replica independently answers within 5 ms 99% of the time and otherwise takes 50 ms or more.

StrategyP(operation slower than 5 ms)
Wait for 1 specific replica1%
Wait for all 3 (W = N)1 − 0.99³ ≈ 2.97%
Wait for 2 of 3 (quorum)P(at least 2 slow) = 3·(0.01²)(0.99) + 0.01³ ≈ 0.03%
Wait for 1 of 30.01³ = 0.0001%

Waiting for a majority of three is roughly a hundred times less likely to hit the slow path than waiting for one specific replica, under these (idealised, independent) assumptions. Real replica latencies are correlated — a shared switch, a shared GC trigger — so the gain is smaller, but the direction holds. Cassandra builds on the same idea with speculative retry: if a replica is slower than a configured percentile, the coordinator sends the read to another replica too.


3. Quorum Intersection Math

3.1 Why W + R > N forces an overlap

Let the write quorum be a set Q_W of W replicas and the read quorum a set Q_R of R replicas, both chosen from N. If they were disjoint, together they would contain W + R distinct replicas. But there are only N replicas, so W + R ≤ N. Contrapositive: if W + R > N, they must share at least

replicas. For N = 3, W = R = 2 the overlap is at least 1. For N = 5, W = R = 3 it is at least 1. For N = 5, W = 4, R = 3 it is at least 2.

This is the pigeonhole principle, and it is the same argument that makes majority-based consensus work (see System Models). The difference is what you do with the overlap: consensus protocols use it to carry promises between rounds; leaderless stores use it to carry the newest version to readers.

3.2 How stale are "partial" quorums?

When W + R ≤ N, a read may miss the latest write. If replicas are chosen uniformly at random and the write has reached exactly W replicas (and no more yet), the probability that a read quorum of R replicas misses all of them is:

NWRP(stale) immediately after write
311C(2,1)/C(3,1) = 2/3 ≈ 67%
321C(1,1)/C(3,1) = 1/3 ≈ 33%
312C(2,2)/C(3,2) = 1/3 ≈ 33%
522C(3,2)/C(5,2) = 3/10 = 30%
523C(3,3)/C(5,3) = 1/10 = 10%
5330 (quorums intersect)

These are worst-case numbers at the instant of acknowledgement. In practice the write keeps propagating to the remaining replicas within milliseconds, so the window of staleness is short. Bailis et al.'s Probabilistically Bounded Staleness (PBS, 2012) models exactly this: given latency distributions, how likely is a read issued t milliseconds after a write to see it? Their measurements found that partial quorums are often consistent within a few milliseconds in practice — useful if you are deciding whether R = 1 is acceptable.

3.3 Beyond majorities: other quorum systems

W and R do not have to be counts. A quorum system is any collection of replica sets with the required intersection property.

  • Weighted quorums: give replicas votes; a quorum is any set holding more than half the votes. Useful when replicas differ in reliability.
  • Grid quorums: arrange N = k × k replicas in a grid; a read quorum is one full row, a write quorum is one full row plus one full column. Every write quorum meets every read quorum and every other write quorum, with quorums of size about 2√N instead of N/2.
  • Flexible Paxos (Howard, Malkhi and Spiegelman, 2016) observed that in Paxos only the phase-1 (leader election) and phase-2 (replication) quorums must intersect each other; two phase-2 quorums need not. So you can replicate to a small quorum in steady state if elections use a correspondingly large one. Same intersection math, applied to consensus.
  • Per-datacenter quorums: Cassandra's LOCAL_QUORUM and EACH_QUORUM restrict or multiply quorums by datacenter (covered in section 9).

4. What Quorums Do Not Guarantee

The intersection rule is a statement about a read that starts after a write has completed successfully, on a fixed set of N replicas, with comparable versions. Every one of those qualifiers is a place where real systems leak.

4.1 Quorums are not linearizable on their own

Linearizability requires that once any read has returned a new value, every later read returns that value or a newer one. A plain quorum read can violate this when a write is in flight — sent but not yet acknowledged by W replicas.

sequenceDiagram
    participant W as Writer
    participant A as Replica A
    participant B as Replica B
    participant D as Replica C
    participant R1 as Reader 1
    participant R2 as Reader 2
    Note over A,D: N=3, W=2, R=2, all replicas hold x=0
    W->>A: write x=1
    Note over A: A applies x=1
    W-->>B: write x=1 (delayed in network)
    W-->>D: write x=1 (delayed in network)
    R1->>A: read x
    R1->>B: read x
    A-->>R1: x=1
    B-->>R1: x=0
    Note over R1: Newest of 2 replies is x=1, return 1
    R2->>B: read x
    R2->>D: read x
    B-->>R2: x=0
    D-->>R2: x=0
    Note over R2: Starts after Reader 1 finished, returns 0
    Note over R1,R2: Reader 1 saw the new value, then Reader 2 saw the old one — not linearizable

Both reads used valid quorums, and W + R > N. The problem is that the write had not yet completed, so the intersection guarantee did not apply — yet Reader 1 still observed it.

The fix: write-back before returning. The classic ABD algorithm (Attiya, Bar-Noy and Dolev, 1995) makes reads linearizable for a single-writer register by adding a second phase: after choosing the newest value, the reader writes it back to a quorum before returning. Then any later read must see it. Cassandra's blocking read repair has a similar effect for quorum reads: when replicas disagree, the coordinator repairs a quorum before returning, which gives monotonic quorum reads. Even then, linearizability for concurrent read-modify-write operations (compare-and-set) needs consensus — which is why Cassandra's lightweight transactions use Paxos (SERIAL consistency).

4.2 Concurrent writes are not ordered

Two clients write different values to the same key at the same time. Each write reaches a different subset of replicas first. With W = 2, both writes can succeed. Which one is "latest"?

  • If versions are wall-clock timestamps, the one with the higher timestamp wins — even if its clock was wrong (section 8).
  • If versions are version vectors, the two are detected as concurrent and both are kept as siblings for the application to merge.

Quorums say nothing about this. They only carry versions; the versioning scheme decides what "newest" means. See Causality, Version Vectors & Dotted Version Vectors.

4.3 Failed writes are not rolled back

If a write reaches fewer than W replicas, the client is told it failed. But the replicas that did receive it keep it — there is no rollback in a leaderless store.

sequenceDiagram
    participant C as Client
    participant A as Replica A
    participant B as Replica B
    participant D as Replica C
    Note over A,D: N=3, W=2, x=0 everywhere
    C->>A: write x=1
    C-xB: write x=1 (B is down)
    C-xD: write x=1 (C is down)
    A-->>C: ack
    Note over C: Only 1 ack, timeout, report FAILED
    Note over C: Client assumes x is still 0
    Note over A,D: Later B and C recover
    Note over A,D: Read repair or anti-entropy copies x=1 from A to B and C
    Note over A,D: The "failed" write becomes the value everyone reads

From the client's perspective a write it was told had failed later appears. Worse, a subsequent read that happens to include A before repair returns x = 1, and a read that does not returns x = 0 — so the value flips depending on which replicas answer. The system has not lost data; it has kept data the client believed was discarded. The safe pattern is to treat a failed write as "unknown outcome" (the Two Generals again) and retry it idempotently until it definitely succeeds, rather than assuming it did not happen.

4.4 The replica set can change under you

The intersection argument assumes the N replicas are fixed. In practice:

  • Sloppy quorums let writes land on nodes outside the N home replicas (section 5). A read of the home replicas may then not intersect.
  • Replacing a node that held a write with a fresh, empty node reduces the number of replicas that have the write — possibly below W — until repair runs.
  • Restoring a node from an old backup can do the same, and can resurrect deleted data.

4.5 Summary

Guarantee people assumeDoes W + R > N give it?
A read after a completed write sees it (on fixed replicas)Yes
Reads never go backwards (monotonic reads) across clientsNo — needs read repair before return or write-back
Linearizability for reads and writesNo — needs ABD-style write-back at minimum
Linearizable compare-and-setNo — needs consensus
Concurrent writes are orderedNo — depends on versioning
Failed writes leave no traceNo
Guarantees hold under sloppy quorumsNo

5. Sloppy Quorums and Hinted Handoff

5.1 The problem

Strict quorums require W of the key's home replicas. If a network partition cuts the client off from two of the three home replicas, writes fail even though plenty of other nodes in the cluster are reachable. For an "always writable" system like Dynamo's shopping cart, that was unacceptable.

5.2 The idea

A sloppy quorum accepts acknowledgements from any W healthy nodes, preferring the home replicas but substituting the next nodes on the ring when home replicas are unreachable. A substitute stores the write together with a hint naming the intended home replica. When the home replica becomes reachable again, the substitute hands off the write and deletes its copy.

sequenceDiagram
    participant C as Coordinator
    participant A as Home A
    participant B as Home B
    participant D as Home C
    participant E as Fallback E
    Note over A,D: Key k lives on A, B, C. N=3, W=2
    C->>A: put(k, v)
    C-xB: put(k, v) (B unreachable)
    C->>D: put(k, v)
    C->>E: put(k, v, hint=B)
    A-->>C: ack
    E-->>C: ack (hinted)
    Note over C: W=2 met with A and E — sloppy quorum succeeds
    D-->>C: ack
    Note over E: E stores v in a hint area for B
    Note over B: B recovers and rejoins
    E->>B: hinted handoff: put(k, v)
    B-->>E: ack
    Note over E: E deletes the hint

5.3 What sloppy quorums cost

Sloppy quorums are an availability mechanism, not a consistency mechanism. While the hint has not been delivered:

  • The write lives on A, C and E. A read from the home replicas B and C (R = 2) intersects at C — fine here. But had the write reached only A and E (W = 2 sloppy), a read from B and C would miss it entirely, even though W + R > N.
  • If the fallback node fails before handing off, the hint is lost; the write survives only on the home replicas that got it, and you depend on anti-entropy to spread it.

So with sloppy quorums, W + R > N no longer guarantees that reads see completed writes. It guarantees durability on W nodes somewhere.

5.4 How real systems treat hints

SystemSloppy quorum?How hints count
Dynamo (2007 paper)YesHinted writes count toward W; the preference list skips unhealthy nodes
Riak KVYes by defaultFallback writes count toward w. Setting pw (primary write) / pr (primary read) requires that many acknowledgements from primary (home) replicas, restoring strict quorum behaviour for those operations
CassandraNo — strict quorumsThe coordinator stores hints for down replicas, but hints do not count toward the consistency level — except for ANY, where a stored hint alone satisfies the write. Hints are kept only for a window (max_hint_window, three hours by default); after that, a node that was down longer must be fixed by repair

That Cassandra row is often misremembered: Cassandra uses hinted handoff as a repair optimisation, not to satisfy quorums.

`ANY` is not a durability guarantee

A Cassandra write at consistency level ANY can succeed with the data stored only as a hint on the coordinator, on no replica at all. If that coordinator then dies, the write is gone. Use it only for data you can afford to lose.


6. Read Repair

Replicas drift apart: a node misses writes while down, a hint expires, a write fails partway. Read repair fixes divergence opportunistically, on the read path, for keys that are actually being read.

6.1 How it works

  1. The coordinator reads from R replicas (or from all N).
  2. It compares versions. If any replica returned an older version, the coordinator sends that replica the newer value.
  3. Depending on the system, the repair is either blocking (finished before the client gets an answer) or asynchronous (fire and forget).

Cassandra optimises step 1 with digest reads: the coordinator asks one replica for the full data and the others only for a hash (digest) of it. If the digests match, it returns the data. If they don't, it fetches full data from the replicas involved, reconciles it (per-cell timestamps), writes the merged result back to the out-of-date replicas, and returns the result.

sequenceDiagram
    participant C as Coordinator
    participant A as Replica A
    participant B as Replica B
    Note over C,B: Read at QUORUM, N=3
    C->>A: full read(k)
    C->>B: digest read(k)
    A-->>C: data v2 @ ts=200
    B-->>C: digest of v1 @ ts=100
    Note over C: Digests differ
    C->>B: full read(k)
    B-->>C: data v1 @ ts=100
    Note over C: Reconcile — v2 has the newer timestamp
    C->>B: repair write v2 @ ts=200
    B-->>C: ack
    C-->>C: return v2 to the client

6.2 Limits of read repair

  • Cold data is never repaired. Keys that are rarely read can stay divergent indefinitely. That is what anti-entropy (next section) is for.
  • Cost on the hot path. Every mismatch adds a round trip and a write. Cassandra once offered probabilistic background read repair (read_repair_chance, dclocal_read_repair_chance) across all replicas; those options were removed in Cassandra 4.0, leaving blocking read repair for the replicas involved in the read.
  • Deletes complicate it. A replica that missed a delete still holds the old value. If the delete marker (tombstone) has already been garbage-collected on the other replicas, read repair will resurrect the deleted value. See section 10.4.

7. Anti-Entropy with Merkle Trees

Anti-entropy is a background process that compares whole replicas and copies over whatever is missing. The challenge is doing this without shipping every key across the network. Merkle trees (hash trees, after Ralph Merkle) solve it: compare a single root hash, and only descend into subtrees that differ.

7.1 Structure

  • Divide the key space (for a replica's token range) into buckets — the leaves.
  • Each leaf stores a hash of all key/version pairs in its bucket.
  • Each internal node stores a hash of its children's hashes.
  • The root hash summarises the entire range.

Two replicas with identical data have identical root hashes. If roots differ, compare children; recurse only into differing children. The amount of data exchanged is proportional to (number of differing leaves) × (tree depth), not to the total number of keys.

7.2 Worked example

Two replicas, A and B, each hold the same token range, split into 8 buckets. Hashes are shown as short made-up hex strings for readability.

Replica A's leaves (bucket → hash): 0:a1 1:b2 2:c3 3:d4 4:e5 5:f6 6:17 7:28

Replica B is identical except bucket 5, where B missed one write: 5:9f

flowchart TB
    subgraph TA["Replica A"]
        RA["root 7e"] --> LA["0-3: 4c"]
        RA --> RRA["4-7: 5d"]
        LA --> LA1["0-1: 11"]
        LA --> LA2["2-3: 22"]
        RRA --> RA1["4-5: 33"]
        RRA --> RA2["6-7: 44"]
        RA1 --> A4["4: e5"]
        RA1 --> A5["5: f6"]
    end
    subgraph TB2["Replica B"]
        RB["root 0b (differs)"] --> LB["0-3: 4c (same)"]
        RB --> RRB["4-7: 8a (differs)"]
        LB --> LB1["0-1: 11"]
        LB --> LB2["2-3: 22"]
        RRB --> RB1["4-5: 6e (differs)"]
        RRB --> RB2["6-7: 44 (same)"]
        RB1 --> B4["4: e5 (same)"]
        RB1 --> B5["5: 9f (differs)"]
    end

The comparison:

StepCompareResultNext
1root: 7e vs 0bDifferCompare both children
2left 0-3: 4c vs 4cSameSkip buckets 0–3 entirely
3right 4-7: 5d vs 8aDifferCompare its children
44-5: 33 vs 6eDifferCompare its children
56-7: 44 vs 44SameSkip buckets 6–7
6bucket 4: e5 vs e5Same—
7bucket 5: f6 vs 9fDifferStream bucket 5's keys

Seven hash comparisons isolate the one bucket that needs syncing, out of a range that might hold millions of keys. Only that bucket's data crosses the network, and within it, the replicas exchange key/version lists to find the specific missing write.

7.3 Code

A minimal Merkle tree and diff in Python, with a self-check:

import hashlib

def h(b: bytes) -> bytes:
    return hashlib.sha256(b).digest()

def leaf_hash(items: dict) -> bytes:
    # Deterministic: sort keys so both replicas hash identically.
    return h(b"".join(k.encode() + b"=" + str(v).encode() + b";" for k, v in sorted(items.items())))

def build(leaves: list[bytes]) -> list[list[bytes]]:
    """Return levels bottom-up: levels[0] = leaves, levels[-1] = [root]. len(leaves) must be a power of 2."""
    levels = [leaves]
    while len(levels[-1]) > 1:
        prev = levels[-1]
        levels.append([h(prev[i] + prev[i + 1]) for i in range(0, len(prev), 2)])
    return levels

def diff(a: list[list[bytes]], b: list[list[bytes]]) -> tuple[list[int], int]:
    """Return (differing leaf indexes, number of hash comparisons)."""
    comparisons, out = 0, []
    def walk(level: int, idx: int):
        nonlocal comparisons
        comparisons += 1
        if a[level][idx] == b[level][idx]:
            return
        if level == 0:
            out.append(idx)
            return
        walk(level - 1, 2 * idx)
        walk(level - 1, 2 * idx + 1)
    walk(len(a) - 1, 0)
    return out, comparisons

def bucket_of(key: str, buckets: int) -> int:
    return int.from_bytes(h(key.encode())[:4], "big") % buckets

if __name__ == "__main__":
    BUCKETS = 8
    data = {f"user:{i}": i for i in range(10_000)}
    replica_a = dict(data)
    replica_b = dict(data)
    replica_b["user:4242"] = -1                    # B holds a stale version of one key

    def tree(rep):
        groups = [dict() for _ in range(BUCKETS)]
        for k, v in rep.items():
            groups[bucket_of(k, BUCKETS)][k] = v
        return build([leaf_hash(g) for g in groups])

    bad, n = diff(tree(replica_a), tree(replica_b))
    assert bad == [bucket_of("user:4242", BUCKETS)]
    assert n <= 2 * 3 + 1                          # at most 2 comparisons per level plus the root
    print("differing buckets:", bad, "comparisons:", n)

7.4 Anti-entropy in real systems

  • Cassandra runs anti-entropy through nodetool repair. Each replica builds Merkle trees over a token range during a validation compaction, the trees are compared, and mismatched ranges are streamed between replicas. Building the trees reads all data in the range, which is why full repair is expensive; incremental repair marks already-repaired SSTables so later runs only consider new data, and tools like Cassandra Reaper schedule repair in small sub-ranges. Operators must run repair on every node more often than gc_grace_seconds (section 10.4).
  • Riak KV offers active anti-entropy (AAE): persistent, continuously updated hash trees per partition, exchanged in the background, so divergence is found without an operator-run job.
  • Dynamo (2007) used Merkle trees per key range for the same purpose.
MechanismRepairsTriggered byCost profile
Hinted handoffWrites missed during short outagesNode rejoiningCheap, bounded by hint window
Read repairKeys that get readReads with mismatched replicasAdds latency to some reads
Anti-entropy (Merkle)Everything, including cold dataSchedule or continuous backgroundHeavy I/O to build trees, network for diffs

A healthy leaderless cluster uses all three: hints for brief outages, read repair for hot keys, and anti-entropy as the backstop.


8. Conflict Resolution: Last-Write-Wins vs Siblings

When replicas hold different versions, the coordinator (or the application) must decide which wins. There are two broad approaches.

8.1 Last-write-wins (LWW)

Attach a timestamp to every write. On conflict, keep the highest timestamp and discard the rest.

  • Cassandra applies LWW per cell (per column value), using a write timestamp — by default assigned by the coordinator in microseconds, or supplied by the client with USING TIMESTAMP. Because resolution is per column, two concurrent updates to different columns of the same row both survive; only updates to the same column conflict.
  • Riak can be configured for LWW (last_write_wins bucket property), which is fast but discards concurrent updates.

LWW has two serious problems:

  1. It silently discards concurrent writes. If two clients add different items to a cart at the same moment, one addition vanishes. There is no error, no log line, no sibling.
  2. It trusts clocks. If node X's clock is 2 seconds ahead, a write coordinated by X at real time t "wins" over any write made elsewhere up to t + 2 s — even a write that causally followed it.

A concrete clock-skew failure:

Real timeEventTimestamp assigned
10:00:00.000Client 1 sets status = "shipped" via node X (clock +2 s)10:00:02.000
10:00:01.000Client 2 reads "shipped", then sets status = "delivered" via node Y (accurate clock)10:00:01.000
LaterReplicas reconcile with LWW"shipped" wins (higher timestamp)

The second write causally depended on the first — Client 2 read "shipped" before writing "delivered" — yet LWW discarded it. LWW is only safe when updates to a key are immutable (write once, never update), naturally commutative, or when losing a concurrent update is genuinely acceptable.

8.2 Siblings (multi-value)

Instead of discarding, track causality with version vectors. When two versions are causally ordered, keep the newer one. When they are concurrent, keep both as siblings and return them to the next reader, who merges them and writes back the result with a context that dominates both.

sequenceDiagram
    participant C1 as Client 1
    participant S as Store (key cart)
    participant C2 as Client 2
    C1->>S: get cart
    S-->>C1: [milk], context V1
    C2->>S: get cart
    S-->>C2: [milk], context V1
    C1->>S: put [milk, eggs] with context V1
    C2->>S: put [milk, bread] with context V1
    Note over S: Both writes descend from V1 but not from each other — concurrent, keep both siblings
    C1->>S: get cart
    S-->>C1: siblings [milk, eggs] and [milk, bread], context V3
    Note over C1: Application merges — union gives [milk, eggs, bread]
    C1->>S: put [milk, eggs, bread] with context V3
    Note over S: New value dominates both siblings, siblings discarded
  • Riak with allow_mult = true works this way: reads may return multiple siblings plus a causal context, and the client is expected to resolve and write back. Riak 2.0 introduced dotted version vectors to keep sibling counts accurate.
  • Dynamo (2007) returned conflicting versions to the application, with the shopping cart merging by union — which famously means deleted items can reappear, since union cannot tell "deleted on one side" from "never added on the other".

Siblings push complexity to the application. Two ways to take it back:

  • Convergent data types: let the store merge automatically using CRDTs — counters, sets with add/remove semantics, maps. Riak 2.0 ships data types built on this idea.
  • Design for commutativity: store events rather than state (append "item added" records), so concurrent writes never conflict.

The mechanics of version vectors, why naïve vectors cause sibling explosion, and how dotted version vectors fix it are covered in Causality, Version Vectors & Dotted Version Vectors.

8.3 Comparison

Last-write-winsSiblings + version vectorsCRDTs
Concurrent updatesOne survives, others silently lostAll kept until mergedMerged automatically
Needs synchronised clocksYes (for correctness of "latest")NoNo
Application complexityNoneMust merge siblingsMust choose data type
Metadata sizeOne timestampVector per value (bounded by replicas with DVVs)Type-dependent, can grow
Typical systemsCassandra, Riak with last_write_winsRiak allow_mult, DynamoRiak data types, many collaborative apps

9. Tunable Consistency

Leaderless stores usually let you choose W and R per request. This is often marketed as "tunable consistency", and the CAP Theorem and Consistency Models pages introduce it. Here are the knobs in detail.

9.1 Cassandra consistency levels

Cassandra's replication factor is set per keyspace (and per datacenter with NetworkTopologyStrategy). The consistency level (CL) is set per request and determines how many replicas must respond.

LevelReads wait forWrites wait forNotes
ANY— (writes only)One node, hints countWeakest; data may exist only as a hint
ONE / TWO / THREE1 / 2 / 3 replicas1 / 2 / 3 replicasAny datacenter
LOCAL_ONE1 replica in the local DC1 replica in the local DCAvoids cross-DC traffic
QUORUM⌊RF_total / 2⌋ + 1 across all DCsSameCross-DC latency on every request in multi-DC clusters
LOCAL_QUORUMQuorum of the local DC's replicasSameMost common for multi-DC: strong within a DC, async across
EACH_QUORUM— (write-oriented)Quorum in every DCExpensive; one DC down blocks writes
ALLAll replicasAll replicasNo fault tolerance
SERIAL / LOCAL_SERIALPaxos readUsed for lightweight transactions (IF NOT EXISTS, IF col = x)Linearizable compare-and-set via Paxos

Rules of thumb for RF = 3 per DC:

  • LOCAL_QUORUM writes + LOCAL_QUORUM reads → overlapping quorums within a DC (2 + 2 > 3). Reads in another DC may be stale until cross-DC replication arrives.
  • ONE + ONE → fastest, frequently stale immediately after writes.
  • QUORUM in a two-DC cluster with RF 3 + 3 means 4 of 6 replicas — at least one remote DC replica per request, so every operation pays cross-DC latency.

For deeper coverage of Cassandra's write path, read path and repair, see Cassandra Internals.

9.2 Riak

Riak exposes the Dynamo knobs directly, per bucket or per request:

ParameterMeaning
n_valReplication factor (default 3)
r, wRead and write quorum sizes (may be satisfied by fallback nodes)
pr, pwHow many primary (home) replicas must respond — use to avoid sloppy-quorum reads/writes
dwHow many replicas must report the write as durable (written to storage backend)
allow_multKeep siblings (true) or resolve with LWW / timestamps (false)

Riak also offers strongly consistent buckets (since 2.0), which use a consensus-style ensemble protocol per key range instead of quorums — an admission that some data needs more than quorums can give.

9.3 DynamoDB is not Dynamo

The name invites confusion. Amazon DynamoDB (the managed service) is not a leaderless Dynamo-style store. According to the 2022 USENIX ATC paper describing its internals, each partition is replicated across three availability zones in a replication group that uses Multi-Paxos for leader election; the leader handles writes and strongly consistent reads, and writes are acknowledged once a quorum of replicas has persisted the log record. Eventually consistent reads (the default) can be served by any replica. See DynamoDB Internals.

DynamoDB optionWhat you getCost
Eventually consistent read (default)Any replica; may miss a very recent write0.5 RCU per 4 KB
Strongly consistent read (ConsistentRead: true)Reflects all writes acknowledged before the read1 RCU per 4 KB (2× the eventual price)
Transactions (TransactWriteItems, TransactGetItems)Serializable multi-item operations2× the normal capacity per item
Global tablesMulti-region, multi-active replicationCross-region conflicts resolved last-writer-wins

So DynamoDB's "tunable consistency" is a choice between reading from the leader and reading from any replica — not a choice of W and R.

9.4 Picking levels: a decision table

RequirementCassandra choice (RF = 3 per DC)Riak choice (n_val = 3)
Fastest possible, staleness OKONE / LOCAL_ONEr=1, w=1
Read-after-write within a regionLOCAL_QUORUM bothr=2, w=2, pr=2, pw=2
Survive a whole DC loss for writes, staleness across DCs OKLOCAL_QUORUM—
Writes must be in every DC before ackEACH_QUORUM—
Unique constraint / compare-and-setSERIAL (LWT)Strongly consistent bucket
Must never lose concurrent updatesModel data so updates don't conflict (separate rows, counters)allow_mult=true or data types

10. Session Guarantees and Edge Cases

10.1 Monotonic reads

Monotonic reads: a client never sees data go "backwards" — once it reads version v, later reads return v or newer. With partial quorums or R = 1, consecutive reads can hit different replicas and violate this.

Ways to get it:

  • Sticky routing: send all of a client's reads to the same replica (breaks when that replica fails).
  • Quorum reads with blocking read repair: a quorum read that has repaired a quorum to version v ensures later quorum reads see at least v.
  • Client-side version tracking: the client remembers the highest version it has seen and rejects (or retries) reads that return older versions.

10.2 Read-your-writes

With W + R > N on fixed replicas, a client's quorum read after its own completed quorum write sees the write. With W = 1 or R = 1 it may not. A common pattern is to write and read the user's own profile at LOCAL_QUORUM while reading other users' content at LOCAL_ONE.

10.3 Concurrent writes and the "lost update"

Leaderless stores have no read-modify-write atomicity. Two clients incrementing a counter by reading 5 and writing 6 will both write 6. Defences:

  • Use a conflict-free type (Cassandra counters, Riak counters).
  • Use compare-and-set via consensus (Cassandra LWT: UPDATE ... IF value = 5).
  • Use siblings and merge with domain knowledge.

10.4 Deletes, tombstones and zombie data

A delete in a leaderless store is a write: it records a tombstone with a timestamp. Tombstones must live long enough to reach every replica; otherwise a replica that missed the delete still holds the old value, and once the tombstones elsewhere are purged, read repair or anti-entropy will copy the old value back — resurrecting the deleted data.

Cassandra keeps tombstones for gc_grace_seconds (default 864,000 s = 10 days). The operational rule follows: every node must be repaired at least once every gc_grace_seconds, and a node that has been down longer than that must not be simply restarted — it should be rebuilt or repaired carefully before rejoining.

10.5 Node replacement

Replacing a failed replica with an empty node temporarily reduces how many replicas hold each write. If a write had reached exactly W = 2 of 3 replicas and one of those two is replaced by an empty node, only one replica now holds it; a quorum read that contacts the empty node and the third replica returns the old value. Bootstrap/streaming and repair fix this, but until they finish, quorum reads can be stale.

10.6 Edge case catalogue

ScenarioWhat goes wrongMitigation
Write in flight during readsNon-monotonic reads across clientsBlocking read repair, ABD write-back
Write fails with < W acks"Failed" write later appearsTreat failures as unknown, retry idempotently
Concurrent writes, LWWOne update silently lostSiblings, CRDTs, or immutable data
Clock skew with LWWCausally later write losesCoordinator timestamps with good NTP, avoid LWW for updates
Sloppy quorumRead misses write on fallbackpr/pw in Riak, strict quorums
Hint expiredReplica missing writes indefinitelyRegular anti-entropy repair
Tombstone purged before repairDeleted data resurrectsRepair within gc_grace_seconds
Node replaced or restored from backupFewer copies than W of recent writesRepair before serving, rebuild as new node
Read-modify-writeLost updatesCAS via Paxos/LWT, CRDT counters

11. Putting It Together: A Quorum Client

A compact TypeScript coordinator that sends writes to all N replicas, waits for W acknowledgements, reads from R replicas, picks the newest version and performs blocking read repair. Versions here are (timestamp, writerId) pairs — LWW semantics — to keep the example short; a real system would plug in version vectors.

type Version = { ts: number; writer: string };
type Versioned<T> = { value: T | null; version: Version };

interface Replica<T> {
  id: string;
  put(key: string, v: Versioned<T>): Promise<void>;          // replica keeps the newer version
  get(key: string): Promise<Versioned<T> | undefined>;
}

const newer = (a: Version, b: Version) =>
  a.ts !== b.ts ? a.ts > b.ts : a.writer > b.writer;          // deterministic tie-break

/** Resolve once `needed` promises fulfil; reject once that becomes impossible. */
function quorum<R>(ps: Promise<R>[], needed: number, timeoutMs: number): Promise<R[]> {
  return new Promise((resolve, reject) => {
    const ok: R[] = [];
    let failed = 0;
    const timer = setTimeout(() => reject(new Error(`timeout: ${ok.length}/${needed}`)), timeoutMs);
    for (const p of ps) {
      p.then(
        (r) => { ok.push(r); if (ok.length === needed) { clearTimeout(timer); resolve(ok); } },
        () => { if (++failed > ps.length - needed) { clearTimeout(timer); reject(new Error("quorum unreachable")); } },
      );
    }
  });
}

export class QuorumCoordinator<T> {
  constructor(
    private readonly replicas: Replica<T>[],   // the key's N home replicas
    private readonly w: number,
    private readonly r: number,
    private readonly self: string,
    private readonly timeoutMs = 200,
  ) {
    if (w < 1 || r < 1 || w > replicas.length || r > replicas.length) throw new Error("bad quorum");
  }

  /** Resolves on W acks. On rejection the outcome is UNKNOWN — some replicas may have the write. */
  async put(key: string, value: T | null): Promise<void> {
    const v: Versioned<T> = { value, version: { ts: Date.now() * 1000, writer: this.self } };
    await quorum(this.replicas.map((rep) => rep.put(key, v)), this.w, this.timeoutMs);
  }

  async get(key: string): Promise<T | null> {
    const replies = await quorum(
      this.replicas.map(async (rep) => ({ rep, v: await rep.get(key) })),
      this.r,
      this.timeoutMs,
    );
    let best: Versioned<T> | undefined;
    for (const { v } of replies) if (v && (!best || newer(v.version, best.version))) best = v;
    if (!best) return null;
    // Blocking read repair: bring every stale replica we heard from up to date before returning,
    // so a later quorum read cannot observe an older value (monotonic quorum reads).
    const stale = replies.filter(({ v }) => !v || newer(best!.version, v.version));
    await Promise.all(stale.map(({ rep }) => rep.put(key, best!)));
    return best.value;                                        // a tombstone is value === null
  }
}

Points worth noticing in the code:

  • put rejecting does not mean the write did not happen — the comment is the most important line.
  • Deletes are writes of null (tombstones), so they participate in versioning and repair.
  • Read repair only touches replicas that answered; replicas that did not respond are left to hints and anti-entropy.
  • The Date.now() timestamp is exactly the clock-skew hazard from section 8.1.

12. War Stories

War Story (illustrative) — the cart that would not forget

An e-commerce team ran a Dynamo-style store with siblings and merged shopping-cart siblings by set union. Customers began reporting that items they had removed kept reappearing. The cause was structural: when one replica saw "remove item X" and a concurrent sibling still contained X, the union of the two contained X again. Union is a correct merge for adds but not for removes. The fix was to model the cart as an observed-remove set (an OR-Set CRDT), which tracks which specific additions a removal observed, so a remove beats only the adds it saw. This is exactly the anomaly the original Dynamo paper describes for its shopping cart.

War Story (illustrative) — ten days and a zombie

A Cassandra cluster's repair job silently stopped running after a configuration change. Nobody noticed for three weeks. During that time one replica missed a batch of deletes while it was briefly overloaded and dropping mutations. Twelve days after the deletes, compaction on the other replicas purged the tombstones (past gc_grace_seconds of 10 days). When repair was finally fixed and ran, it found the overloaded replica holding the old rows and no tombstones elsewhere — and dutifully streamed the "missing" rows back to every replica. Deleted user records reappeared in production. The post-mortem action items: alert on time-since-last-successful-repair per node, and treat repair as a correctness requirement rather than maintenance.

War Story (illustrative) — the fast clock

A service wrote user preferences to Cassandra with client-supplied timestamps. One application host's NTP daemon had failed, and its clock drifted several minutes ahead. Every write from that host "won" against writes from all other hosts for minutes into the future, so users who changed their settings again on another host saw their changes silently revert. Nothing errored. The team switched to coordinator-assigned timestamps, added clock-offset monitoring with alerting on every host, and moved the most contended settings to a lightweight-transaction (Paxos) path.


13. Decision Guide

Use leaderless quorum replication when:

  • Write availability matters more than ordering — writes must succeed even when replicas are down or partitioned.
  • Data is naturally conflict-free or easy to merge — append-only events, time series, immutable blobs, counters, sets.
  • Tail latency matters — waiting for the fastest W or R replicas hides slow nodes.
  • You can operate repair — anti-entropy is not optional.

Prefer a leader-based or consensus-based design when:

  • You need linearizable reads and writes, or compare-and-set (unique usernames, inventory decrements, leases) on most operations.
  • You need multi-key transactions.
  • The team cannot run regular repair or reason about siblings.
WorkloadGood fit?Why
IoT / metrics ingestionYesAppend-only, high write volume, staleness OK
User activity feedsYesWrites are independent events
Shopping cartYes, with CRDT mergeConcurrent adds/removes must merge correctly
Session storeYesSingle writer per key mostly, staleness tolerable
Bank balancesNoNeeds atomic read-modify-write and invariants
Unique username registrationOnly via LWT / consensusNeeds compare-and-set
Distributed locks / leader electionNoNeeds consensus — see Distributed Locking

Interview Questions

1. Explain N, W and R. Why does W + R > N give "strong" reads, and what exactly does it guarantee?

N is the number of replicas per key, W the number of acknowledgements required for a write, R the number of replies required for a read. If W + R > N, any read quorum and write quorum share at least W + R − N replicas (pigeonhole), so a read starting after a write completed contacts at least one replica holding it, and with comparable versions the coordinator can return it. It does not guarantee linearizability (in-flight writes), ordering of concurrent writes, or anything under sloppy quorums.

2. Show a non-linearizable execution with N=3, W=2, R=2.

All replicas hold x=0. A write of x=1 reaches A but is delayed to B and C. Reader 1 reads A and B, sees x=1 (newest) and returns 1. Reader 2 then reads B and C, both still 0, and returns 0. Reader 2 started after Reader 1 finished, yet saw an older value. Fix: readers write back the newest value to a quorum before returning (ABD), or use blocking read repair.

3. What is a sloppy quorum and what does it trade away?

When home replicas are unreachable, a sloppy quorum accepts acknowledgements from other healthy nodes, which store the write with a hint and hand it off when the home replica returns. It trades consistency for write availability: with writes on fallback nodes, a read of home replicas may not intersect the write set even if W + R > N. Riak uses sloppy quorums by default (pr/pw restore strictness); Cassandra does not — its hints don't count toward consistency levels except ANY.

4. Compare hinted handoff, read repair and anti-entropy.

Hinted handoff: coordinators/fallbacks hold writes for down replicas and replay them on recovery — cheap, but bounded by a hint window. Read repair: during reads, out-of-date replicas are updated — fixes hot data, adds read latency, never touches cold data. Anti-entropy: background comparison of replicas using Merkle trees, streaming differing ranges — catches everything but costs I/O. You need all three; anti-entropy is the safety net.

5. How do Merkle trees reduce the cost of replica comparison? Work through an example.

Each leaf hashes a bucket of keys; parents hash children; the root summarises the range. Replicas compare roots and recurse only into differing subtrees. With 8 buckets and one differing bucket, about 2 comparisons per level (≈7 total) isolate the bucket, after which only that bucket's keys are exchanged. The cost scales with the number of differing buckets times tree depth, not with total keys.

6. Why is last-write-wins dangerous? When is it acceptable?

LWW discards all but the highest-timestamped concurrent write silently, and trusts clocks — a fast clock makes its writes win even over causally later writes. It is acceptable when data is immutable (write-once keys), when updates are idempotent overwrites where losing a concurrent one is fine, or when conflicts are designed out (e.g., per-column updates that never overlap).

7. A write fails with only 1 of 3 acks at W=2. What state is the system in?

Unknown outcome. One replica holds the new value and it won't be rolled back. Reads that include that replica may return it, others won't, until read repair or anti-entropy propagates it everywhere — at which point the "failed" write becomes the value. Clients should retry the write idempotently rather than assume it didn't happen.

8. What is the difference between Cassandra's QUORUM and LOCAL_QUORUM, and when would you use EACH_QUORUM?

QUORUM requires a majority of all replicas across all datacenters, so in multi-DC clusters every request pays cross-DC latency. LOCAL_QUORUM requires a majority of the local DC's replicas — strong within the DC, asynchronous across DCs. EACH_QUORUM requires a quorum in every DC for writes — used when data must be durable in every region before acknowledging, at the cost that any DC outage blocks writes.

9. Is DynamoDB a leaderless Dynamo-style system?

No. Per its 2022 USENIX ATC paper, each DynamoDB partition is a replication group across three AZs using Multi-Paxos for leader election; the leader serves writes and strongly consistent reads, and writes are acknowledged after a quorum persists the log record. Eventually consistent reads can go to any replica. The Dynamo paper's leaderless design lives on in Cassandra, Riak and Voldemort, not in DynamoDB's internals.

10. How can deleted data come back to life in Cassandra?

A delete writes a tombstone. If a replica misses the tombstone and the other replicas purge it after gc_grace_seconds (10 days by default), the next read repair or anti-entropy run sees the old value on one replica and no tombstone elsewhere, and copies the old value back. Prevention: repair every node within gc_grace_seconds and never bring a long-dead node back without rebuilding it.

11. What is the probability that a read at N=5, W=2, R=2 misses a just-acknowledged write?

If the write is on exactly 2 random replicas and the read picks 2 random replicas, P(miss) = C(3,2)/C(5,2) = 3/10. With W=3, R=3, the quorums intersect and P(miss)=0. In practice writes keep propagating, so the stale window is usually short (see PBS).

12. How would you implement a unique-username constraint on Cassandra?

Not with quorum reads and writes — two concurrent registrations can both read "not taken" and both write. Use a lightweight transaction: INSERT INTO usernames (name, user_id) VALUES (...) IF NOT EXISTS, which runs Paxos among replicas (SERIAL / LOCAL_SERIAL) and returns whether it applied. Accept the extra round trips for this path only.