Part 4 · Redundancy

Replication II: Multi-Leader, Leaderless, Quorums, and Conflicts

Lesson 08 gave us one leader: every write went through a single node, followers caught up behind it, and the cost was replication lag plus a failover scramble when that one writer died. But one writer is also a bottleneck and a single point of failure — a user in Singapore still pays a round-trip to a leader in Virginia, and an offline app cannot write at all. This lesson lifts the "one writer" assumption. Once several nodes can accept writes, you buy local low-latency writes and survive a node loss without a failover — but you inherit a new, harder problem: two writes to the same record can happen with no agreed order between them, and the system must decide what "the value" even is. This is the home of the quorum condition w + r > n.

DDIA source

Arc drawn from Martin Kleppmann, Designing Data-Intensive Applications, Chapter 5 (Replication) — the multi-leader and leaderless (Dynamo-style) sections, quorum reads/writes, and conflict resolution. Original synthesis; ML-infra framings are ours.

Linear position

Prerequisite: Lesson 08 — single-leader replication, the replication log, async vs sync acks, replication lag, and read-your-writes. We build directly on "a write must reach replicas" and do not re-derive it.
New capability: Reason about systems where more than one node accepts writes; size a leaderless quorum so reads see the latest write; and choose a conflict-resolution strategy that does not silently drop data.

The plan

Five moves. (1) Multi-leader replication — why you'd accept more than one writer, and the write conflict it forces on you. (2) Leaderless (Dynamo-style) replication — clients write to many replicas and read from many, with read repair and anti-entropy holding them together. (3) The quorum condition w + r > n built from first principles, with worked numbers, plus what breaks when w + r ≤ n. (4) A quorum widget: turn the n/w/r knobs and watch the overlap appear or vanish. (5) Conflict resolution — last-write-wins and why it loses data, version vectors that detect concurrency, and CRDTs / app-level merge that resolve it without loss.

1 · Multi-leader: local writes, global conflicts

What this is: let several nodes accept writes — and pay for it in conflicts.

In single-leader replication (lesson 08) exactly one node accepts writes; everyone else is a read-only follower. Multi-leader replication (also called master-master or active-active) relaxes that: more than one node accepts writes, and each leader is also a follower of the others, streaming its writes to them. Two situations make this worth the trouble:

→Multi-datacenter. Put a leader in each region. A user writes to the nearest leader at LAN latency (~1 ms) instead of crossing an ocean to a single global leader (~150 ms), and a whole datacenter can go offline while the others keep accepting writes.

→Offline-capable clients. A phone or laptop editing a calendar or notes is effectively a leader with a local database; it accepts writes while disconnected and syncs when it reconnects. Every device is a tiny datacenter.

(A third case is real-time collaborative editing — a shared doc or whiteboard, where each user's client applies edits locally and syncs to the others, exactly the offline-client pattern at sub-second scale.) The thing you buy is availability and local latency. The bill arrives as the write conflict: the same logical record edited in two leaders before either has heard from the other. User A in the EU sets their display name to "Sam"; at the same wall-clock moment User A on their phone (in the US region) sets it to "Samantha". Each leader accepts its write locally and is correct locally. When the two writes replicate and meet, there is no single "happened-before" order between them — they are concurrent — and the system must decide what the name now is.

Multi-leader is not a free availability button

Single-leader replication never has a write conflict: all writes pass through one node, so there is always an order. The instant you admit a second writer you have signed up to detect concurrency and resolve it. "Multi-leader" is really a promise that conflicts on this data are acceptable and resolvable — true for a shopping cart or a notes app, false for a bank balance or a "username is unique" constraint, which is exactly why those stay single-leader.

2 · Leaderless: write to many, read from many

What this is: no leader at all — the client writes to many replicas and reads from many.

Leaderless replication (the Dynamo-style design behind Cassandra, Riak, and Amazon's DynamoDB lineage) drops the idea of a leader entirely. There are n replicas of each piece of data. To write, the client (or a coordinator acting for it) sends the write to all n replicas and waits for w of them to acknowledge. To read, the client queries several replicas and waits for r of them to respond, then uses the freshest value among the responses. There is no failover step (lesson 08) because there is no leader to fail — a down replica is just one fewer ack, and writes keep flowing.

leaderless write/read with n = 3 replicas, w = 2, r = 2 write(k = v2) read(k) |-- replica A ok ┐ |-- replica A -> v2 ┐ |-- replica B ok ┘ w=2 acks: DONE |-- replica C -> v1 ┘ r=2 responses |-- replica C slow/down (no ack) (A and C disagree -> read repair) the read touched A; A also took the write -> the read sees v2. it also noticed C is stale at v1 -> it writes v2 back to C (read repair).

Two background mechanisms stop a leaderless store from drifting apart forever:

Read repair. When a read collects responses from several replicas and notices one is stale (an older version than another), it writes the newer value back to the stale replica. Reads thus opportunistically heal the data they touch — great for frequently-read keys, useless for keys no one reads.
Anti-entropy. A background process that continuously compares replicas and copies over missing or stale values, covering the rarely-read keys read repair never touches. The naive way to compare two replicas holding millions of keys is to ship every key and value across the network and diff them — far too expensive to run continuously. The standard fix is a Merkle tree, and its mechanism is worth seeing.

Mechanism — how a Merkle tree finds the difference in log(N) hashes

A Merkle tree (hash tree) summarizes a replica's whole keyspace as one number, then lets two replicas zoom in on exactly where they disagree without shipping the data. Build it bottom-up: split the key range into many small buckets, hash the contents of each bucket into a leaf, then hash each pair of children into a parent, repeating up to a single root hash that fingerprints the entire range.

root = H(H1 + H2) <- one hash per replica / \ H1 = H(a+b) H2 = H(c+d) / \ / \ a=H(keys b=H(keys c=H(keys d=H(keys 0–24%) 25–49%) 50–74%) 75–99%) compare two replicas, top-down: roots equal? -> identical, done. (one comparison covers everything) roots differ? -> compare H1, H2. only the differing subtree is opened say H1 equal, H2 differs -> descend only into H2 ... down to the one leaf bucket that differs -> sync just those keys

The payoff is the descent: if the two replicas are identical, a single root-hash comparison proves it — no data moves at all. If they differ in one bucket, you follow only the path whose hashes mismatch and ignore every subtree whose hashes match, so you localize the divergence in about log(N) hash comparisons instead of an N-key scan, and you ship only the handful of keys in the differing leaf. That is what makes anti-entropy cheap enough to run forever in the background; Dynamo and Cassandra use exactly this, and equal root hashes across replicas are the "evidence it is correct" in this lesson's Where is truth? artifact below.

Why does this give you anything safe? Because of how w and r are sized relative to n — the quorum condition, next.

3 · The quorum condition: w + r > n

What this is: size the read and write sets so they are forced to share a node.

Here is the whole idea in one line: if the write set and the read set must overlap, then a read is forced to touch a node that took the latest write. A quorum is "enough nodes that any two such groups must share at least one member." Among the replicas a read contacts, that shared node holds the newest value — and since the read uses the freshest response it gets, it sees the latest write.

When must a set of w nodes and a set of r nodes (both drawn from n replicas) be forced to overlap? Think of the worst case: the write hit one group of w nodes, the read hit a different group of r nodes, and they avoided each other as much as possible. They can stay disjoint only while w + r fits inside n without touching. The moment

w + r > n

there are too many nodes between the two sets to keep them apart — by the pigeonhole principle they must share at least one node. That shared node took the write and is in the read, so the read sees it. That is the entire guarantee.

Worked numbers

n = 3, w = 2, r = 2. Then w + r = 4 > 3 ✓. Any 2 of 3 replicas plus any other 2 of 3 must share at least one (you cannot pick two disjoint pairs from three nodes). The read sees the latest write. Failure tolerance: a write needs 2 acks, so it survives n − w = 1 replica being down; a read needs 2 responses, so it also survives n − r = 1 down. This is the classic default — strong-ish reads, tolerate one node loss on each path.

n = 5, w = 3, r = 3. Then w + r = 6 > 5 ✓, overlap guaranteed. Now you tolerate 5 − 3 = 2 down replicas on each of the read and write paths — more durable and more fault-tolerant, at the cost of waiting for 3 acks/responses instead of 2 (higher tail latency, since you wait for the 3rd-slowest node).

The trade is a dial. Want fast writes, accept staleness? Set w = 1, r = 1 with n = 3: w + r = 2 ≤ 3 — no overlap guarantee. Want read-heavy with strong reads? Set w = n, r = 1: every write goes everywhere, any single replica is current. The condition w + r > n is the line between "a read is guaranteed to see the latest committed write" and "maybe not."

What breaks when w + r ≤ n

Take n = 3, w = 1, r = 1 (w + r = 2 ≤ 3). A write acks after hitting only replica A. A later read is served by only replica C, which never got the write yet. The read returns the old value — a stale read, even though the write "succeeded." No overlap was forced, so the read and write sets missed each other. This is not a bug; it is exactly the consistency you asked for when you set the numbers that low. Leaderless quorums let you choose this on purpose for speed — you just must know you chose it.

The fine print (sloppy quorums and hinted handoff). Even with w + r > n, a quorum is weaker than a leader. Two caveats matter most. First, a sloppy quorum: when some of the n "home" replicas are unreachable, the system can accept the w acks from other reachable nodes outside the home set rather than failing the write. This raises write availability, but the write landed on nodes that are not in the read's home set, so the overlap guarantee no longer holds until the data is moved back — temporarily, even w + r > n can return stale reads. The repair step is hinted handoff: the stand-in node holds the write with a "hint" of where it really belongs and forwards it to the proper home replica once that node comes back. Sloppy quorum + hinted handoff is a tunable relaxation: it trades the overlap guarantee for staying writable during partial outages.

4 · Feel the knobs: the quorum widget

Set n, w, and r below. The widget draws the n replicas as a ring, shows one worst-case write set (blue) and read set (amber) pushed as far apart as possible, marks any node that is in both (the overlap, green), and tells you whether w + r > n holds and how many node failures each path tolerates.

Quorum overlap — does every read see the latest write?

Blue = the w nodes a write reached. Amber = the r nodes a read reached, placed to avoid the write set as much as possible (worst case). Green = a node forced into both sets — that is the overlap that guarantees the read sees the write. If no node turns green, a stale read is possible.

n (replicas): 3 w (write acks): 2 r (read responses): 2

w + r vs n

—

Read sees latest write?

—

Write tolerates down

—

Read tolerates down

—

Show the core JS

// w and r are each capped at n (can't ack more nodes than exist).
// place the write set on nodes [0 .. w-1]; place the read set as far away
// as possible, on the LAST r nodes [n-r .. n-1]. they overlap iff those
// ranges touch, i.e. iff (w - 1) >= (n - r), i.e. iff w + r > n.
const overlap = (w + r > n);            // the quorum condition
const writeTolerates = n - w;           // down replicas a write survives
const readTolerates  = n - r;           // down replicas a read survives

5 · Conflict resolution: detect first, then resolve without losing data

What this is: tell "one write followed the other" from "they were concurrent" — then merge without loss.

Whether conflicts came from two leaders (§1) or two concurrent leaderless writes (§2), you face the same question: two values exist for one key. The key distinction is order. If write B saw A's effect and built on it, B happens-after A and simply supersedes it — no conflict. If neither saw the other, they are concurrent, and that is a true conflict you must resolve. There are three families of answer, in increasing safety.

Last-write-wins (LWW), and why it silently drops data

Last-write-wins attaches a timestamp to every write and, on conflict, simply keeps the one with the larger timestamp and discards the rest. It is appealingly simple and it always converges — every replica ends up agreeing. The catastrophe is the word "discards": LWW silently drops the losing write. If "Sam" and "Samantha" were genuinely concurrent edits, LWW throws one away with no record that it ever existed — and worse, it decides the winner by clock order, which is not causal order. Clocks on different machines drift (lesson 15 makes this precise); a write that physically happened later can carry an earlier timestamp and lose. LWW is acceptable only when losing concurrent writes is genuinely fine (e.g., a cache entry, an idempotent "last seen" timestamp).

Version vectors: detect that two writes were concurrent

To do better than guessing, the system must first know two writes were concurrent rather than one following the other. A version vector (a generalization of a vector clock to per-replica counters) does this: each replica keeps a counter, and a value carries the vector of counters it has "seen." Given two versions, you can compare their vectors — if one vector is element-wise ≥ the other, that write causally happened-after and supersedes it; if neither dominates, the writes are concurrent and you have a true conflict. The point is detection, not resolution: the version vector turns "two values exist" into "these two values are causally concurrent siblings" so the system can stop pretending one is simply newer.

Siblings, CRDTs, and application merge: resolve without loss

Once concurrency is detected, you have honest options that don't drop data:

Keep siblings. Store both concurrent values and return them together on the next read (Dynamo/Riak do this). The application — or the user — merges them. The shopping-cart classic: if one device added "milk" and another added "eggs" concurrently, return both carts and union the items, so nothing is lost.
CRDTs (Conflict-free Replicated Data Types). Data types whose merge rule is mathematically guaranteed to converge regardless of order — e.g., a grow-only set, an add/remove set, or a counter. The structure is the conflict resolution: any two replicas that have seen the same writes compute the same merged value automatically. This is what powers offline-capable collaborative apps.
Application-level merge. Domain-specific logic: union the cart, take the max of a high-water mark, run operational transforms on a text document. Right when the domain has a meaningful merge; the cost is you must write and test that merge function.

The recurring lesson: conflict resolution belongs in the data model. A shopping cart merges by union; a collaborative doc uses CRDTs; a bank balance cannot merge by averaging and so should not be multi-writer at all. Choosing multi-leader or low-quorum leaderless is choosing to make these decisions explicit instead of letting a clock make them for you.

Trade-offs

Choice	Buys	Costs
Multi-leader	Local low-latency writes, region/datacenter independence, offline edits	Write conflicts you must detect and resolve
Leaderless quorum	No leader to fail over, tunable read/write/durability via n, w, r	Read repair + anti-entropy machinery; richer anomaly surface
w + r > n	Read guaranteed to see the latest committed write	Higher tail latency (wait for more acks/responses)
Sloppy quorum + hinted handoff	Stays writable during partial outages	Temporarily breaks the overlap guarantee until handoff completes
Last-write-wins	Trivial, always converges	Silently drops concurrent writes; trusts unreliable clocks
Version vectors + siblings / CRDT / merge	Detects concurrency; resolves without data loss	More storage and a domain-specific merge to write

Failure modes

LWW data loss. Concurrent writes silently collapse to one, chosen by a possibly-skewed clock. Symptom: edits "disappear" with no error.
Quorum sized too low. w + r ≤ n ships stale reads that look like a caching bug. Symptom: a value you just wrote isn't there on the next read from another replica.
Sloppy-quorum staleness. During a partition, writes land outside the home set; reads briefly miss them even though w + r > n. Symptom: transient stale reads correlated with node outages.
Repair falls behind. Rarely-read keys never get read-repaired and anti-entropy is throttled; replicas diverge for a long time. Symptom: cross-region feature values disagree though every node is "healthy."
Conflict shoved onto data that can't merge. Multi-writer on a balance or a uniqueness constraint — there is no safe automatic merge.

Decision checklist

Does this data tolerate conflicts (cart, notes) or forbid them (balance, unique key)? If it forbids them, keep it single-leader (lesson 08).
If leaderless: pick n, then choose w and r for your read/write mix; verify w + r > n if you need fresh reads.
How many simultaneous replica failures must each path survive? That sets n − w and n − r.
Are you using a sloppy quorum? If so, document that fresh-read guarantees lapse during outages.
What detects concurrency — timestamps (LWW, lossy) or version vectors (honest)?
What merges siblings — a CRDT, an app-level merge, or the user? Is that merge tested?
Is read repair on, and is anti-entropy keeping up under load?

Checkpoint exercise

Try it

You run a leaderless feature store with n = 3 replicas serving an online model. (a) Online inference reads a user's features and must not see a stale value after a profile update — pick w and r and show the arithmetic that guarantees it, and state how many replica failures each path now tolerates. (b) A batch backfill writes millions of feature rows and you want it fast and highly available; which knob do you lower, and what consistency do you give up for the next reader? (c) Two regions concurrently update a user's "tags" set — propose a conflict-resolution strategy that loses no tags, and say what data type makes it automatic.

Where this points next

Replication answered "how do we keep copies of the same data consistent?" — whether behind one leader (08) or many writers (this lesson). Multi-leader had a striking limit case: a phone or laptop that accepts writes while disconnected and syncs later is just a leader with a flaky, often-broken link to the others. Push that to the extreme and you get local-first software, where the device's own copy is the primary and the network is a best-effort sync channel rather than a precondition for writing. The next lesson, Local-First and Offline Sync (lesson 10), takes the conflict machinery you just built — version vectors, CRDTs, sibling merge — and runs it at the edge: every device is its own leader, sync is intermittent, and convergence-without-data-loss stops being an option and becomes the whole design. It is the most aggressive form of the redundancy this part is about, and the natural close before we leave copies behind and start splitting the data itself.

Where is truth?

In a leaderless or multi-leader store, there is no single node that holds the truth — and naming that honestly is the whole point. System of record: the set of replicas taken together, reconciled by the rules below; no one replica is authoritative. Copies / derived views: the n replicas of each key, plus any read-repaired or hinted-handoff copies sitting temporarily on stand-in nodes. Freshness budget: set by the quorum sizing — w + r > n promises a read sees the latest committed write, while w + r ≤ n (or a sloppy quorum mid-partition) admits a bounded staleness window you chose on purpose. Owner: the keyspace/partition owner that holds the n-replica set and runs its repair processes. Deletion path: a delete is itself a write and must propagate as a tombstone to w replicas, then linger long enough for anti-entropy to overwrite every straggler — delete too eagerly and a stale replica resurrects the value. Reconciliation / repair path: read repair on the keys reads touch, plus background anti-entropy (Merkle-tree compare-and-sync) for the cold keys; conflicts surface as version-vector siblings merged by CRDT or app logic. Evidence it is correct: matching Merkle-tree root hashes across replicas, a shrinking divergence/repair backlog, and version vectors showing no undetected concurrent siblings.

Takeaway

Admitting more than one writer buys availability and local latency but forces you to handle write conflicts. Multi-leader replication suits multi-datacenter and offline clients; leaderless (Dynamo-style) replication drops the leader entirely — clients write to w of n replicas and read from r, with read repair and anti-entropy holding them together. The central knob is the quorum condition w + r > n: it forces the read and write sets to overlap on at least one node, so a read is guaranteed to see the latest committed write; when w + r ≤ n stale reads become possible by design, and sloppy quorums trade even that guarantee for write availability during outages. Resolve the conflicts that follow by detecting concurrency with version vectors (never trusting last-write-wins, which silently drops data on a possibly-skewed clock) and then merging without loss via siblings, CRDTs, or an application merge — because conflict resolution belongs in the data model, not in the clock.

Interview prompts

When would you choose multi-leader over single-leader replication, and what new problem does it create? (§1 — multi-datacenter and offline clients gain local low-latency writes and independence; the cost is write conflicts, since two leaders can accept concurrent edits to one record with no agreed order.)
State and justify the quorum condition. (§3 — w + r > n forces any write set of w and read set of r drawn from n replicas to share at least one node (pigeonhole), so the read touches a replica holding the latest write and sees it.)
With n = 5, you want to survive two replica failures on reads and still read fresh. Give w and r. (§3 — r = 3 tolerates 5 − 3 = 2 down on reads; pick w = 3 so w + r = 6 > 5. w = 3 also survives 2 down on writes.)
What goes wrong with n = 3, w = 1, r = 1? (§3 — w + r = 2 ≤ 3; the write may ack on one replica and the read may hit a different one, returning a stale value. Fast, but no fresh-read guarantee.)
Why is last-write-wins dangerous, and what should replace it? (§5 — it silently discards concurrent writes and decides by clock order, which isn't causal order and is subject to clock skew; detect concurrency with version vectors, then keep siblings / use a CRDT / merge in the app.)
What are read repair and anti-entropy, and why do you need both? (§2 — read repair heals stale replicas on the keys reads happen to touch; anti-entropy is a background compare-and-sync (often Merkle trees) that reaches the rarely-read keys read repair never sees.)
What does a sloppy quorum with hinted handoff buy and cost? (§3 — it accepts w acks from nodes outside the home set so writes stay available during a partition; the cost is that the overlap guarantee lapses until the stand-in hands the write off to its true home replica.)