Consistency in Replicated Stores: Reading the Guarantees

"Strongly consistent" appears in the documentation of systems that provide materially different things. The word is not standardised, and the gap between what a vendor means and what you assume is where the surprising bugs live.

For a separate people-operations perspective, the overview covers what Microsoft Teams activity indicators do and do not show.

What follows is the vocabulary needed to read those claims, and the questions that get an unambiguous answer.

Why replication forces the question

Data lives on several machines. A write arrives at one. Until it reaches the others, they hold a different value.

The system must decide what a read sees in the meantime, and every choice is a trade. Wait for all replicas and reads are correct but slow and fragile — one slow replica affects every operation. Serve immediately from whichever replica is nearest and reads may be stale.

CAP is the usual framing and it is narrower than it is quoted. It says that during a network partition you must choose between consistency and availability. It says nothing about the normal case, where the real trade is between consistency and latency — often written as PACELC: during a Partition, choose Availability or Consistency; Else, choose Latency or Consistency.

The second half is the one that governs your system almost all of the time, and it is the half that gets left out.

The models, from strongest down

Linearizability

Every operation appears to take effect at a single instant between its start and completion, and all clients see one consistent order. Once a write completes, every subsequent read anywhere returns that value or a later one.

This is what most people mean by "strongly consistent." It is the model that behaves like a single machine.

Cost: cross-replica coordination on the critical path. In a geographically distributed system that means at least one round trip between regions, per operation.

Sequential consistency

All clients see operations in the same order, but that order need not respect real time. A write may become visible to everyone some time after it completed. Weaker than linearizability and rarely offered as a named option.

Causal consistency

Operations that are causally related are seen in the same order by everyone. Concurrent operations may be seen in different orders by different clients.

In practice this prevents the anomalies people actually notice: you do not see a reply before the message it replies to, and you do not see a comment on a post that has not appeared.

It does not require cross-replica coordination on writes, which makes it much cheaper than linearizability and available during partitions. For a great many applications it is the right point on the curve, and it is under-used because it is under-advertised.

Eventual consistency

Replicas converge if writes stop. That is the entire promise: no bound on when, no ordering guarantee, no statement about what you see in the meantime.

"Eventually" is not a duration. Under normal conditions it may be milliseconds. During a partition it is however long the partition lasts.

The session guarantees, which matter more than the model name

These are the ones that determine whether your application looks broken to a user, and they can be provided on top of a weak model.

Read your writes. After you write, your own subsequent reads see it. Without this, a user updates their profile, the page reloads from a lagging replica, and their change appears to have been lost. This is the single most common visible symptom of replication in a web application.

Monotonic reads. You never see time move backwards. Without it, refreshing a page can show newer data, then older data, as requests land on different replicas.

Monotonic writes. Your own writes are applied in the order you issued them.

Writes follow reads. If you read a value and then write based on it, the write is ordered after that read everywhere.

A system offering eventual consistency plus read-your-writes and monotonic reads is usable for most applications. One offering eventual consistency alone is not, without the application doing the work.

Implementing the ones you need

Read your writes is usually achieved by routing a client's reads to the primary for a period after a write, or by having the client carry a version token that the replica must have caught up to before serving. The second is better — it degrades to a small wait rather than to primary overload.

Monotonic reads by pinning a session to one replica, or again by carrying a version token.

A common shortcut worth naming: "read from the primary for 5 seconds after a write." It works most of the time, it fails when replication lag exceeds the window, and the failure is invisible in testing because staging has no lag. If you use it, monitor replication lag and alert when it approaches the window.

Quorum reads and writes

Common in systems that let you tune this per operation. With N replicas, a write to W of them and a read from R of them, the overlap when W + R > N means a read sees at least one replica with the latest write.

What quorums do not give you:

Not linearizability by themselves. Concurrent operations, failed writes that reached some replicas, and read repair timing all create cases quorum arithmetic does not cover.

Not protection from last-write-wins conflicts. If the system resolves conflicts by timestamp, quorums do not help — see clocks in distributed systems.

Not a fixed guarantee if N changes. During a failure or a rebalance, the effective N differs from the configured one.

Questions that get a straight answer

When evaluating a system, these are unambiguous and the documentation usually answers them if you look:

After a write returns success, is it guaranteed to survive the loss of the node that accepted it? Some systems acknowledge before replicating. This is a durability question and it is separate from consistency.

Can a read return a value older than one the same client already read?

Can a read return a value older than one the same client wrote?

What happens during a partition — reject writes, or accept on both sides and reconcile later?

If both sides accept, how is the conflict resolved? Last-write-wins by timestamp is the answer that should make you pause.

Is the guarantee per key or across keys? Many systems provide strong guarantees for a single key and nothing across keys. A read of two related keys can see an inconsistent combination.

What is the observed replication lag under load? Not the design target — the measured p99 in your environment.

Design so you need less

The cheapest consistency is the kind you did not require.

Keep data that must be consistent together in one place. Cross-partition consistency is where the cost is. Choosing partition keys so that related data lands together removes the problem rather than solving it.

Make operations commutative where you can. Two increments applied in either order give the same answer; two absolute sets do not. Conflict-free data types formalise this.

Use versions rather than reading before writing. UPDATE ... WHERE version = $expected detects a conflict without needing a consistent read first.

Accept staleness where it is harmless, deliberately. A view count, a recommendation list and a search index can all be seconds behind with no consequence. An account balance cannot. Making that decision per field, explicitly, is cheaper than applying one setting to everything.

Show staleness rather than hiding it. A visible "updated 30 seconds ago" is better than an interface that implies data is live when it is not.

The summary

"Strongly consistent" is not a defined term. Ask whether it means linearizable, and ask what happens during a partition.

Session guarantees matter more than the model name for user-facing behaviour. Read-your-writes and monotonic reads prevent nearly all the symptoms users report.

CAP describes the partition case; PACELC describes the other 99% of the time, and the latency-versus-consistency trade is the one you live with daily.

And the most useful design move is to need less consistency — by keeping related data together and by deciding per field how stale it is allowed to be.