Copies that agree

Why replicate

• Availability: if one copy is unreachable, another can answer.
• Latency: a copy near the user avoids a cross-continent round trip.
• Read throughput: many copies can serve reads in parallel.

The cost falls on writes. Every update must reach every copy, and until it does, copies disagree. Replication improves reads and resilience, but it raises write latency and coordination work, and the cost grows with the number of replicas and the strength of the consistency promised. More replicas do not make everything faster.

Who accepts writes

Sync, async, and lag

With synchronous replication, the leader waits for followers to confirm before acknowledging a write. No acknowledged write is lost if the leader dies, but one slow follower stalls every write. With asynchronous replication, the leader acknowledges immediately and ships changes in the background. Writes are fast, but followers lag behind and a leader crash can lose recent writes. Many systems compromise: one synchronous follower, the rest asynchronous.

Consistency models

Data-centric consistency models describe what every client can observe, ordered from strongest to weakest.

Linearizability

The system behaves like a single copy. Each operation appears to take effect at one instant between its call and its return, so real-time order is respected.

Sequential consistency

All clients see operations in one total order that respects each client's own program order, but not necessarily real time.

Causal consistency

Operations related by happened-before are seen in that order everywhere; concurrent operations may appear in different orders on different replicas.

Eventual consistency

If updates stop, replicas eventually converge. Nothing is promised about reads in the meantime.

"Strong consistency" is an informal phrase; linearizability is the precise term. The difference between linearizable and sequential is real time, as this history shows:

Linearizability is what makes locks, leader election, and unique constraints safe, and it costs coordination on every operation. Causal consistency is about as strong as a model can be while every replica stays available during a network partition, which makes it a popular target for geo-replicated systems.

PapersHerlihy & Wing, "Linearizability: A Correctness Condition for Concurrent Objects," ACM TOPLAS 12(3), 1990 · Lamport, "How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs," IEEE Trans. Computers, 1979 · Ahamad et al., "Causal Memory," Distributed Computing 9(1), 1995 · Viotti & Vukolić, "Consistency in Non-Transactional Distributed Storage Systems," ACM Computing Surveys 49(1), 2016
ExploreJepsen consistency models map

Client-centric guarantees

Many applications don't need global agreement. They need each user's own view to make sense. Session guarantees, introduced with the Bayou system, give exactly that on top of eventually consistent replicas:

Typical implementations route a user's reads to the replica that took their writes, or attach a version token to each session and only read from replicas that have caught up to it.

PapersTerry et al., "Session Guarantees for Weakly Consistent Replicated Data," PDIS 1994 · Vogels, "Eventually Consistent," CACM 52(1), 2009

Quorums

In a leaderless system with N replicas, a write succeeds once W replicas confirm it, and a read queries R replicas and keeps the newest version it sees. If R + W > N, every read set overlaps every write set, so a read always reaches at least one replica holding the latest acknowledged write.

Overlap alone does not make a system linearizable. Concurrent writes, failed writes that partially succeeded, and sloppy quorums (accepting writes on stand-in nodes during failures, then handing them back later) can all expose stale or out-of-order values. In practice, measurements show that even non-overlapping settings are usually fresh within milliseconds, which is why many deployments accept the risk.

PapersGifford, "Weighted Voting for Replicated Data," SOSP 1979 · DeCandia et al., "Dynamo," SOSP 2007 · Bailis et al., "Probabilistically Bounded Staleness for Practical Partial Quorums," PVLDB 5(8), 2012

Repairing divergence

Replicas drift apart whenever a write misses some of them. Three mechanisms bring them back together:

• Read repair: when a read sees replicas with different versions, it writes the newest version back to the stale ones.
• Hinted handoff: a node that accepted a write for an unreachable replica keeps a "hint" and delivers it when that replica returns.
• Anti-entropy: replicas periodically compare their contents in the background. Comparing Merkle trees (hash trees over key ranges) lets two replicas find differences by exchanging a few hashes instead of all their data.

PapersDemers et al., "Epidemic Algorithms for Replicated Database Maintenance," PODC 1987 · Merkle, "A Digital Signature Based on a Conventional Encryption Function," CRYPTO 1987

Resolving conflicts

When two replicas accept different writes to the same item concurrently, the system must pick a result. The options range from simple and lossy to precise and more complex.

A conflict-free replicated data type (CRDT) defines a merge that is commutative, associative, and idempotent. Replicas can then exchange state in any order, any number of times, and still converge. A grow-only counter is the simplest example:

PapersTerry et al., "Managing Update Conflicts in Bayou," SOSP 1995 · Shapiro et al., "Conflict-Free Replicated Data Types," SSS 2011 · Kleppmann et al., "Local-First Software," Onward! 2019

Choosing a point

CAP says that during a network partition a replicated system must choose between answering every request (availability) and never returning stale data (linearizability). PACELC adds the everyday case: even with no partition, stronger consistency costs latency, because replicas must coordinate before answering.

The choice can be made per operation. A shop can read its catalog from any replica while checking out against a linearizable inventory count. Systems like Cassandra, DynamoDB, and MongoDB expose this as a per-request setting.

-- Cassandra: choose consistency per statement (N = 3)
CONSISTENCY ONE;     -- fastest; may read stale data
CONSISTENCY QUORUM;  -- 2 of 3; R + W > N when both use QUORUM
CONSISTENCY ALL;     -- every replica; any failure blocks

PapersBrewer, "CAP Twelve Years Later," IEEE Computer 45(2), 2012 · Abadi, "Consistency Tradeoffs in Modern Distributed Database System Design," IEEE Computer 45(2), 2012
DocsDynamoDB read consistency · MongoDB read concern

In practice

Tools and reading