Leaderless Replication: Quorums and Conflicts

Leaderless replication removes the write authority

Leader-follower replication gives one node the job of ordering writes. Leaderless replication removes that authority: any replica can accept a write, either directly from the client or through a coordinator. A coordinator forwards requests, but it does not define one global order.

This is why leaderless systems can keep working through individual node failures, latency spikes, and some network interruptions. It is also why conflicts and stale reads become part of the design instead of something a leader hides.

flowchart LR
  C[Client] -->|write to several replicas| R1[(Replica 1)]
  C -->|write to several replicas| R2[(Replica 2)]
  C -->|write to several replicas| R3[(Replica 3)]
  R3 -. temporarily unavailable .- C

A write can succeed while one replica misses it

Suppose a value has three replicas. The client sends the write to all three in parallel. If two replicas acknowledge it, the write is considered successful even when the third is offline. There is no leader failover because there is no leader to promote.

The cost appears when the unavailable replica returns. It may still hold an old value, so a client must read from several replicas, compare returned versions, and identify the newest state.

sequenceDiagram
  participant W as Writer
  participant R1 as Replica 1
  participant R2 as Replica 2
  participant R3 as Replica 3
  participant Q as Reader
  W->>R1: write v7
  W->>R2: write v7
  W-xR3: write v7
  R1-->>W: ok
  R2-->>W: ok
  Note over W: 2 acknowledgements: success
  Q->>R1: read
  Q->>R2: read
  Q->>R3: read
  R1-->>Q: v7
  R2-->>Q: v7
  R3-->>Q: old v6
  Q->>R3: repair with v7

Read repair and anti-entropy close the gap

Read repair fixes a stale replica when a read exposes it: the client sees the newest value from another replica and writes it back. It is effective for frequently read keys.

Anti-entropy is a background reconciliation process. Replicas compare their state and copy missing values even if no application read discovers the problem. Unlike a leader replication log, it need not copy updates in one order, so convergence may take time.

💡 Read repair alone leaves rarely read keys at risk. If no anti-entropy process exists, an old replica may retain a value for an unbounded time. Eventual consistency needs an operational definition: measure or estimate staleness, not just assume replicas will catch up.

Quorum math creates overlap

For one value, n is the number of designated replicas, w is the number of write acknowledgements required, and r is the number of replicas consulted by a read. The usual overlap condition is w + r > n.

flowchart TB
  W[Successful write] --> A[Replicas 1, 2, 3]
  R[Successful read] --> B[Replicas 3, 4, 5]
  A --> O((Replica 3 overlaps))
  B --> O
  O --> F[At least one read replica saw the write]

With n = 3, w = 2, and r = 2, one node can be unavailable. With n = 5, w = 3, and r = 3, two nodes can be unavailable. Requests commonly go to all n replicas in parallel; w and r say how many successful responses are enough to finish.

The settings are workload tradeoffs. For example, w = n and r = 1 gives fast reads, but one failed replica blocks every write. Lower w or r can improve availability and latency, while making stale reads more likely.

A quorum is useful, not a promise of perfect freshness

Even with w + r > n, a read can be stale. A read may race a write, concurrent writes may have no natural order, a partially failed write may survive on some replicas despite being reported as failed, or a newer replica may later be restored from an older copy.

Quorums therefore tune the probability and cost of stale results. They do not automatically provide read-your-writes consistency, monotonic reads, consistent-prefix reads, or linearizability. Stronger guarantees usually require transactions or consensus.

Sloppy quorums choose availability over home-replica overlap

During a network problem, a client may be unable to reach enough of a key's designated home replicas even though other database nodes are reachable. A strict quorum returns an error. A sloppy quorum stores the write on reachable temporary nodes instead.

flowchart LR
  C[Client] --> H1[Home replica 1]
  C --> H2[Home replica 2 unavailable]
  C --> T[Temporary replica]
  T -->|hinted handoff after recovery| H2

Hinted handoff later moves that temporary write to the intended home replica. This improves write availability, but the temporary node may not be in the r replicas queried by a later read. It preserves data on w nodes somewhere, not the usual read-write overlap.

💡 Multi-datacenter leaderless systems often acknowledge a local quorum first, keeping user-facing latency independent of a slow cross-region link while remote replicas catch up asynchronously. Cassandra and Voldemort can include replicas from several datacenters in n; Riak commonly keeps n local to one datacenter and replicates between clusters in the background.

Concurrent writes need a resolution model

Different replicas can receive the same two writes in different orders. Blindly overwriting on arrival makes their final state diverge permanently. The replicas must instead converge on a shared result.

flowchart LR
  A[Client A writes X = A] --> N1[Node 1: A]
  A --> N2[Node 2: A then B]
  B[Client B writes X = B] --> N2
  B --> N3[Node 3: B then A]
  A --> N3
  N1 --> X[Arrival order alone cannot decide the result]
  N2 --> X
  N3 --> X

Last-write-wins forces convergence by picking one winner, usually from a timestamp. That may be acceptable for a cache or a replaceable preference, but it silently discards other acknowledged writes. It is safest only when a key is written once and then treated as immutable, such as a unique UUID-keyed record.

💡 Convergence is not correctness. A latest-preference value may safely win; a set of labels may safely merge; a shared document may need preserved versions or a human decision. Money, inventory, and reservations usually need coordination or rejection, not automatic merging.

Causality separates overwrites from conflicts

A happens before B when B knew about, depended on, or built on A. Two operations are concurrent when neither knew about the other. Physical time is not the test: operations minutes apart can still be concurrent if a network delay kept them unaware of each other.

A versioned write tells the database which earlier state the client observed. The database may overwrite values at or below that observed version, but it must retain values from later, concurrent branches. Those surviving concurrent values are often called siblings.

flowchart TD
  E[Empty cart] --> M[Add milk]
  E --> G[Add eggs]
  M --> F[Add flour]
  G --> H[Add ham]
  F --> B[Add bacon]
  F --> S1[Sibling: milk, flour, eggs, bacon]
  H --> S2[Sibling: eggs, milk, ham]

Clients must read before writing, send the observed version with their write, and merge all values returned by the earlier read. The server can identify causal relationships from versions without understanding the business meaning of the value.

Merging is part of the data model

A shopping cart can often merge siblings by taking their union. But deletion makes that unsafe: one device may remove a book while another adds headphones, and a naive union brings the book back. A tombstone is a versioned deletion marker that keeps the removal visible during merging.

💡 Merge at write time when a deterministic rule is truly safe, such as a set-union of labels. Resolve at read time when a person must choose, such as two incompatible document edits. Never hide a business-rule conflict behind generic merge logic: two valid bookings can still reserve the same room and time.

CRDTs are data structures designed to merge certain concurrent updates automatically. They can reduce application merge work, but only when their semantics match the product rule.

Version vectors extend causal tracking across replicas

One counter is insufficient when several replicas accept writes. A version vector keeps a version component per replica, describing which changes a value has observed. Replicas send this causal context to clients on reads, and clients return it with later writes.

Version vectors distinguish a genuine overwrite from a concurrent write. A client can read from one replica and write to another without losing data, although that may create siblings that still require correct merging.

What I will check in a real system

I will ask which data can tolerate stale reads, which operations must never be lost, what w, r, and n mean for availability, whether anti-entropy exists, how staleness is measured, whether sloppy quorums are enabled, and who owns sibling resolution. The right replication design follows the meaning of the data, not a default database setting.

These are my personal learning notes from Designing Data-Intensive Applications by Martin Kleppmann.