Multi-Leader & Leaderless Replication
Let more than one node accept writes and you gain availability, local latency and offline editing. You also inherit a question a single leader never faces: when two writes disagree, which one is true?
The whole idea
Beyond one leader
Leader-based replication puts every write through one node. That gives you one history and no conflicts, and three problems:
- Every write pays the leader’s latency. If the leader is in Virginia, a user in Sydney waits on the Pacific for every write.
- The leader is a single point of failure for writes. Failover takes time, and it can lose writes or split the brain.
- Some clients can’t reach any leader. A phone on a plane still wants to add a calendar event.
The alternatives all let more than one node accept writes. Multi-leader replication has several leaders, typically one per region or one per device, that exchange changes. Leaderless replication drops the idea of a leader entirely: the client (or a coordinator acting for it) writes to several replicas directly.
Both share a cost a single leader never pays: two writes to the same data can be accepted in two places at once, with neither knowing about the other. Most of this lesson is about what to do then.
Multi-leader replication
Give each region its own leader. Inside a region, replication is ordinary leader-and-followers. Between regions, leaders forward each other’s changes asynchronously.
A leader per region
The wins over one global leader are real:
- Latency. Writes complete in the local region; the cross-region hop happens in the background.
- Tolerance of region and network failures. Each region keeps accepting writes while cut off, and catches up later. There is no failover to perform.
The same shape appears in less obvious places. A calendar app that works offline is a multi-leader system in which every device is a leader: its local database accepts writes and syncs when it gets a connection, possibly days later. Collaborative editors are the extreme case, where every keystroke is a write on a different “leader”. That’s the setting that motivates local-first software, which keeps the primary copy of data on your devices and treats the server as one more replica.
Between leaders, changes flow along a topology. All-to-all is the most robust, but messages can overtake each
other: an update can arrive before the insert it modifies. Ring and star topologies avoid some of that but break
when one node in the path fails. Each change also carries the IDs of the nodes it has passed through, so a change
doesn’t loop forever. PostgreSQL 16 added exactly this to logical replication: a subscription with
origin = none ignores changes that themselves arrived by replication, which makes two-way replication between
two PostgreSQL servers possible without loops.
Write conflicts
Two truths at once
With a single leader, the second edit would either wait for the first or see it. With two leaders, both succeed locally, and the conflict is only discovered later, asynchronously, when the user has long moved on. You can’t ask them to retry. There are three strategies:
- Avoid conflicts. Give each record a home leader and route all writes for it there: a user’s data lives in their home region. It’s the most common approach in practice because it sidesteps the problem, until the home region fails and you re-route, at which point conflicts are back.
- Converge automatically. Every replica applies the same deterministic rule so they all end at the same value. The usual rule is last write wins. Others merge the values (concatenate, take the union) or use data types designed to merge, which is where CRDTs come in.
- Keep the conflict and resolve it in the application. Store all conflicting versions and let application code (or a person) merge them, either when the conflict is detected or the next time the data is read.
A conflict isn’t always two writes to one field. Two people booking the same meeting room in different regions both succeed, and only the invariant (one booking per room per slot) is violated. No merge function can fix that after the fact; the fix is routing those writes to one leader.
Last write wins
The simplest way to converge: attach a timestamp to every write, and when versions disagree, keep the one with the highest timestamp. Last write wins (LWW) is what Cassandra does for each column of each row, and what DynamoDB global tables do per item in their default multi-Region mode.
It converges, which is the point. But “last” is defined by clocks, and clocks on different machines disagree.
When the later write loses
LWW is safe only when concurrent writes to the same key are either impossible or don’t matter, such as when each key is written once (an immutable event with a unique ID) or when losing one of two simultaneous edits is acceptable. Applied to data that is genuinely updated concurrently, it loses writes at alarming rates. In Kyle Kingsbury’s 2013 Jepsen tests of Riak with last-write-wins, concurrent clients writing to one key lost most of their acknowledged writes, without any network partition. Under a partition, LWW with quorum reads and writes lost about 91%. A CRDT set with union merge, under a partition too, lost none.
Leaderless replication
Amazon’s Dynamo paper (SOSP 2007) described a key-value store for services like the shopping cart, built to be “always writeable”: a customer adding an item must never see an error, even mid-outage. It has no leader at all. Its design inspired Cassandra, Riak and Voldemort.Not to be confused with Amazon DynamoDB, a different system despite the name. DynamoDB elects a leader per partition with Multi-Paxos, so within a Region it is leader-based.
The core idea:
- Each key has n replicas. A write is sent to all n in parallel, and succeeds once w acknowledge.
- A read is sent to all n, and returns once r respond. Each response carries a version, and the newest wins.
- A replica that was down simply misses writes. Nothing like failover happens; the stale copy gets fixed later.
In practice the client usually talks to a coordinator, any node in the cluster, which fans out to the replicas
on its behalf. Cassandra calls this choice a consistency level: ONE, QUORUM, ALL, and multi-datacentre
variants like LOCAL_QUORUM (a majority in the local datacentre only).
Quorums
Choose w + r > n, and every read set overlaps every write set in at least one replica, so at least one of the r replies has the latest successful write.
Why w + r > n works
The knobs trade off against each other. With n = 3, w = 2, r = 2 you tolerate one unavailable replica for both reads and writes. With w = n and r = 1, reads are fast but one dead replica blocks writes. Making w or r smaller than a quorum gives lower latency and higher availability at the cost of stale reads, which is often a sensible choice, as long as it’s a deliberate one.
Even with w + r > n, quorums are not linearizable. The edge cases are where real systems bite:
- Concurrent writes to one key need a resolution rule. If it’s LWW, writes are lost as above.
- A write that fails (fewer than w acknowledgements) is not rolled back on the replicas that did take it. Later reads may or may not see it.
- A write concurrent with a read may be visible on some replicas only, so the read may return either value.
- A node restored from a stale replica can drop the number of replicas holding a new value below w.
- Sloppy quorums break the overlap entirely, as the next section shows.
Quorums give you a probability of fresh reads, not a proof. Measuring staleness, rather than assuming none, is the operational answer: how many replicas lag, and by how long.
Sloppy quorums
What if a network fault cuts the client off from most of a key’s n “home” replicas? A strict quorum fails the write. Dynamo instead chose a sloppy quorum: write to the first n healthy nodes in the key’s preference list, even if some aren’t home replicas. A stand-in node keeps the write along with a hint naming the intended recipient, and forwards it when that node is reachable again: hinted handoff.
Writes that land in the wrong place
It’s a straight trade: writes succeed as long as any w nodes are reachable, but a read of r home replicas may not
see them. Cassandra kept hinted handoff but not the sloppy quorum. Its consistency level counts acknowledgements from
the key’s own replicas: at QUORUM the coordinator waits for a majority of them, and stores a hint for a replica that
is down or times out. Only ANY lets a hint stand in for a replica: “a single replica may respond, or the coordinator
may store a hint”. Hints are best effort. A coordinator keeps them for up to max_hint_window, three hours by
default, and a replica down longer than that stays out of sync until read repair or anti-entropy repair reaches it.
Read repair and anti-entropy
A leaderless system has no log for a stale replica to replay. Two mechanisms make replicas converge instead:
- Read repair. When a read sees replicas disagree, it writes the newest version back to the stale ones, as in the hero diagram. It’s cheap and effective for data that’s read often, but it never fixes data nobody reads.
- Anti-entropy. A background process compares replicas and copies whatever is missing. Comparing every key would mean shipping the whole dataset. Instead, each replica builds a Merkle tree: leaves hash ranges of keys, parents hash their children. Two replicas compare top-down and descend only where hashes differ.
Finding one difference in a billion keys
Cassandra does both. Since version 4.0, read repair runs only in the foreground, blocking the read, when replicas
consulted at the requested consistency level disagree; the old probabilistic background read repair was removed.
Anti-entropy is nodetool repair, which builds Merkle trees per token range. Incremental repair (the default)
checks only data written since the last repair, so occasional full repairs are still needed.
Detecting concurrent writes
LWW pretends there’s an order between any two writes. Often there isn’t. Two writes are concurrent when neither knew about the other, no matter what the clocks say, and the honest response is to keep both until something merges them.
The trick is to version each key. Every write says which version it was based on. If a write is based on the latest version, it replaces it. If it’s based on an older one, the writer hadn’t seen the newer write, so the two are concurrent and both are kept as siblings.
Two devices, one cart
With many replicas each accepting writes, one number per key isn’t enough. Each replica keeps its own counter for the key, and the set of counters is a version vector. Comparing two vectors tells you whether one version descends from the other (every counter ≥) or whether they’re concurrent (each is ahead somewhere). Dynamo used vector clocks and truncated them at about ten entries; Riak later adopted dotted version vectors to stop siblings multiplying under heavy concurrency.
This is exactly how Amazon’s shopping cart behaved: adds were never lost because the merge was a union, but deleted items could resurface, since a union can’t tell “removed” from “never added”. In practice concurrency was rare: over 24 hours, 99.94% of cart requests saw one version, and the paper attributes most divergent versions to busy robots, not humans.
CRDTs
Merging siblings by hand in every application is error-prone. A CRDT (conflict-free replicated data type) is a data structure designed so that replicas can update it independently and always merge to the same result, whatever order updates arrive in. The idea was formalised by Shapiro, Preguiça, Baquero and Zawirski in 2011: if merging is commutative, associative and idempotent, replicas converge. They called this strong eventual consistency.
A counter that can't lose a like
The same trick generalises:
- Counters: a grow-only counter (as above); a PN-counter pairs two of them for increments and decrements.
- Sets: an observed-remove set tags each add with a unique ID, so a remove deletes only the adds it saw. A concurrent re-add survives, which fixes the cart’s resurrection problem.
- Registers and maps: an LWW register is a CRDT too. It converges, but it still drops one of two concurrent writes.
- Sequences: text CRDTs give each character a unique, ordered ID, so concurrent insertions interleave deterministically. These power collaborative editors.
CRDTs are not free. They carry metadata (tombstones, IDs, per-replica counters), they can’t enforce invariants like “balance ≥ 0” or “one booking per slot”, and choosing the merge semantics is still a design decision.
Trade-offs
| Single leader | Multi-leader | Leaderless | |
|---|---|---|---|
| Who accepts writes | one node | one leader per region or device | any w of n replicas |
| Write latency | to the leader, maybe cross-region | local | the w-th fastest replica |
| On node or region failure | failover, possible lost writes | others keep writing | nothing to fail over; tolerates n − w down |
| Write conflicts | none | yes, resolved asynchronously | yes, resolved on read or repair |
| Read freshness | strong from leader, stale from followers | stale across regions | tunable via r, never linearizable |
| Repairing stale copies | replay the log | replay each leader’s log | read repair, hinted handoff, anti-entropy |
In the real world
- Amazon Dynamo (2007) introduced the leaderless toolkit used here: (n, r, w) quorums with (3, 2, 2) as the common setting, sloppy quorums, hinted handoff, vector clocks with application-level reconciliation, and Merkle-tree anti-entropy, all to meet a 300 ms target at the 99.9th percentile.
- Apache Cassandra is the most widely deployed descendant: per-query consistency levels, LWW per cell, hinted handoff for up to three hours, blocking read repair, and Merkle-tree repair that operators must schedule. Version 5.0 shipped in 2024.
- Amazon DynamoDB global tables are multi-leader across Regions. The default mode replicates asynchronously,
typically within a second, and resolves concurrent writes to an item by last writer wins. Since June 2025, a
multi-Region strong consistency mode runs in exactly three Regions (or two plus a witness), replicates each write
synchronously to at least one other Region before acknowledging it, for a zero recovery point, and rejects a
write to an item that’s being modified in another Region with a
ReplicatedWriteConflictException. - Riak exposed siblings and vector clocks directly to applications, then shipped built-in CRDTs (counters in 1.4, sets and maps in 2.0) and dotted version vectors to curb sibling explosion.
- Figma built multiplayer editing on ideas “inspired by” CRDTs but, by its own account, not true CRDTs: a central server is the authority, and concurrent changes to the same property of the same object resolve by last writer wins at the server. Centralising removed much of the CRDT overhead.
- Automerge, a CRDT library from the local-first research community, released version 3.0 in 2025, cutting memory use by more than 10× by keeping document history compressed at runtime.
Pitfalls
- Treating LWW as conflict resolution. It’s conflict deletion. Use it only for data written once, or where losing a concurrent write is acceptable.
- Believing w + r > n means strong consistency. Concurrent writes, failed writes, sloppy quorums and restored replicas all return stale data with a quorum. Quorums are not linearizable.
- Running a leaderless store without scheduled repair. Read repair only fixes what’s read; without anti-entropy inside the tombstone window, deleted data comes back.
- Conflict avoidance that forgets failover. Home-region routing works until a region fails and writes move, and then the conflicts you avoided arrive at once.
- Expecting a merge function to protect invariants. Uniqueness and “never negative” need coordination, not merging.
- Confusing Dynamo with DynamoDB. One is a 2007 leaderless design; the other is a leader-per-partition managed service.
Recall
Go deeper
- DeCandia et al., “Dynamo: Amazon’s Highly Available Key-value Store” (SOSP 2007): the source of quorums, sloppy quorums, hinted handoff and vector clocks in production. Read sections 4 and 6.
- Kyle Kingsbury, “Jepsen: Testing the Partition Tolerance of PostgreSQL, Redis, MongoDB and Riak” (InfoQ, 2013): measured data loss under LWW, quorums and sloppy quorums, and a CRDT that lost nothing.
- Apache Cassandra docs: consistency levels, hints, read repair and repair: how a leaderless store converges in practice, and the operational duty it leaves you.
- Shapiro, Preguiça, Baquero, Zawirski, “Conflict-free Replicated Data Types” (SSS 2011): the formal basis: state- and operation-based CRDTs and the conditions for convergence.
- Kleppmann, Wiggins, van Hardenberg, McGranaghan, “Local-first software” (Onward! 2019): why every device as a leader is a design goal, and where CRDTs fit.
- Evan Wallace, “How Figma’s multiplayer technology works” (2019): a pragmatic middle ground: CRDT ideas with a central authority.
- AWS docs, “How DynamoDB global tables work”: multi-Region LWW and the newer strongly consistent mode, side by side.
Keep going
The atomic notes for this lesson live in the knowledge graph:
Next on the map: Sharding (splitting data across nodes, which every Dynamo-style store does alongside replication) and Consistency Models (what “stale” and “linearizable” mean precisely).