Can Multi-Leader and Leaderless Replication Achieve Linear Consistency?

Multi‑Leader Replication and Linear Consistency

Building on a previous article about distributed leader replication, the author explains that multi‑leader (or multi‑active) architectures introduce write conflicts and replication lag, making linear consistency unattainable for both exclusive and shared data. Even with monotonic reads/writes confined to a single data‑center leader, failures or network partitions force the system to fall back to eventual consistency.

When a write is issued to IDC1’s leader and later to IDC2’s leader before replication completes, the second write may see stale data, leading to conflict resolution challenges.

For exclusive data, the author proposes a client‑side double‑write approach, but notes that node failures, dropped requests, and the need for WAL or retry mechanisms re‑introduce inconsistency risks.

Shared data faces even higher conflict complexity, and the architecture’s high availability comes at the cost of strong consistency.

Leaderless Replication and Linear Consistency

Leaderless replication removes a designated leader, allowing any replica to accept writes. The NWR (N‑replicas, W‑writes, R‑reads) model is introduced: if W + R > N, a read is guaranteed to intersect with at least one replica that has the latest write.

Examples with a 5‑replica cluster show how different W and R settings affect availability and consistency. Setting W = R = (N + 1)/2 (rounded up) is common, but real‑world fault scenarios (node crashes, network partitions) can still break linear consistency.

Quorum‑based NWR cannot fully guarantee linear consistency because failures may prevent reaching the required quorum, leading to stale reads.

Sloppy Quorums and Hinted Hand‑Off

When network failures reduce the number of reachable replicas, Sloppy Quorums allow writes/reads to succeed on alternative nodes, while Hinted Hand‑Off later forwards those writes to the intended replicas. This improves fault tolerance but does not restore linear consistency, as reads may still return older values.

Summary

Single‑leader replication can achieve linear consistency for exclusive data when reads are directed to the same leader.

Multi‑leader replication cannot guarantee linear consistency due to write conflicts and replication lag.

Leaderless replication with quorum (NWR) offers a best‑effort approach; its ability to provide linear consistency depends on W + R > N and on whether the system uses sloppy quorums or not.

Overall, achieving linear consistency in multi‑data‑center deployments involves trade‑offs between availability, performance, and complexity.