Consistency Models: From Linearizability to Eventual

The payment page says a charge succeeded. The customer refreshes, and the order is still unpaid. They try again. Ten minutes later, two charges appear. Every server behaved according to its local data, replication recovered exactly as designed, and the system still broke its promise to the person using it.

That promise is a consistency model: a set of rules describing which values a read may return when operations overlap, replicas lag, clients move between regions, or a network link fails. “Strong” and “eventual” are useful shorthand, but they are not designs. A team needs to know which orderings users can observe, which anomalies are acceptable, and where coordination is worth its latency and availability cost.

Consistency is also not the same as transaction isolation. Consistency models usually describe visibility and ordering across copies of data. Isolation describes how concurrent transactions interact. A database can offer linearizable reads of committed state while still permitting write skew under snapshot isolation; another can serialize transactions on one leader while a follower read remains stale. The product contract must cover both dimensions where both matter.

Consistency is an observable ordering contract #

Model an execution as a history $H$ of invocation and response events. We write $a \prec_H b$ when operation $a$ completes before operation $b$ begins in real time. A register is linearizable when its completed operations can be arranged into a legal sequential history $S$ such that:

Each operation appears to take effect at one instant between its call and return, its linearization point. If Alice’s write returns before Bob starts a read, Bob must observe that write or a later one. Concurrent operations may be ordered either way. Linearizability composes across objects, which makes local reasoning powerful: if each register is linearizable, their collection remains linearizable. Implementations usually pay with leader coordination, consensus, or quorum protocols, especially during failures.

Sequential consistency also requires one legal total order that preserves every client’s program order, but it does not preserve real-time order between clients. Bob may begin after Alice’s completed write and still read the old value if the global sequence can place Bob’s read before Alice’s write without reversing either client’s own operations. This difference is invisible in some batch workloads and startling in interactive products.

The models below are not a single perfectly nested ladder. Causal consistency and session guarantees constrain different relationships, and a system can combine them.

Causality and sessions preserve human expectations #

Real time is often stronger than a feature needs. Causality captures the order in which information could have influenced other information. If operation $a$ precedes $b$ in one process, if $b$ reads a value written by $a$, or if those relationships connect transitively, then $a$ happens before $b$:

A causally consistent system never exposes $b$ without its prerequisite $a$. If Linh posts “The migration is finished” and Minh replies “Great, I will deploy,” nobody should see the reply before the original post. Two unrelated reactions are concurrent and may appear in different orders. Vector clocks, dependency sets, or hybrid logical clocks can track enough context to delay an effect until its causes are present, though metadata and cross-region waiting grow with the design.

Session guarantees offer a practical client-centered vocabulary:

• Read your writes: after changing an avatar, the same session does not show the old avatar.
• Monotonic reads: once a session has observed version 12, it never later sees version 11.
• Monotonic writes: one client’s writes become visible in the order issued.
• Writes follow reads: a write made after reading version 12 is ordered after that version.

Together, these guarantees approach causal behavior for one client without requiring every read worldwide to be linearizable. A gateway can attach a version token to the session, route the next request to a sufficiently current replica, or wait until the selected replica catches up. Tokens must survive reconnects and region changes if the product calls those interactions one session. Sticky routing alone is fragile: a replica restart or failover can silently erase the guarantee.

Be precise about scope. Read-your-writes for one account does not prevent two support agents from overwriting each other. Monotonic reads do not ensure a multi-key page is a consistent snapshot. A dashboard can show an invoice total from version 20 beside line items from version 18, a fractured read, even though each key individually moves forward.

Eventual convergence and the real meaning of quorums #

Eventual consistency promises convergence, not a deadline and not a particular conflict outcome. Informally, if no new updates occur and all accepted updates are eventually delivered, replicas approach equivalent state:

The system still needs a deterministic merge rule. Last-write-wins is simple but can discard a valid update when clocks skew or two users edit concurrently. Version vectors expose concurrency but require conflict resolution. CRDTs converge by construction for supported data types, yet product semantics still matter: merging two shopping carts by set union may resurrect an item a customer removed. “Eventually the same” says nothing about whether the final state is correct for the business.

Consider a write acknowledged by one replica before replication reaches another:

For $N$ replicas, teams often choose read quorum $R$ and write quorum $W$. The inequality $R + W > N$ means every read set intersects every write set. Requiring $W > N/2$ also makes write sets intersect. Intersection is useful, but it is only geometry. Nodes must compare versions correctly, deal with concurrent writers, repair stale copies, and define what happens when a quorum cannot be reached.

The following TypeScript-like pseudocode sketches an ABD multi-writer atomic register. A tag is ordered lexicographically by counter and writer ID. Reads perform a write-back phase; omitting it can let a value observed from a partial write disappear from later reads.

type Tag = readonly [counter: number, writerId: string];
type Versioned<T> = { tag: Tag; value: T };

interface Replica<T> {
  query(): Promise<Versioned<T>>;
  store(candidate: Versioned<T>): Promise<void>; // keeps max tag
}

declare function majority<T>(requests: Array<Promise<T>>): Promise<T[]>;
declare function maxByTag<T>(values: Versioned<T>[]): Versioned<T>;

async function read<T>(replicas: Replica<T>[]): Promise<T> {
  const observed = await majority(replicas.map((replica) => replica.query()));
  const latest = maxByTag(observed);
  await majority(replicas.map((replica) => replica.store(latest)));
  return latest.value;
}

async function write<T>(
  replicas: Replica<T>[],
  writerId: string,
  value: T,
): Promise<void> {
  const observed = await majority(replicas.map((replica) => replica.query()));
  const latest = maxByTag(observed);
  const next: Versioned<T> = {
    tag: [latest.tag[0] + 1, writerId],
    value,
  };
  await majority(replicas.map((replica) => replica.store(next)));
}

Under its assumptions of reliable links, crash-stop nodes, unique writers, and a live majority, the protocol implements a linearizable register. Production systems add retries, deduplication, membership epochs, persistence, and bounded resources. A Dynamo-style quorum with sloppy quorums, hinted handoff, last-write-wins, or changing membership has different guarantees. Never infer a model from the letters $N$, $R$, and $W$ alone.

CAP and PACELC describe tradeoffs, not architecture labels #

CAP applies when a network partition prevents some nodes from communicating. A partition-tolerant system must then choose between consistency, commonly interpreted as linearizability for the discussed register, and availability, meaning every request to a non-failing node eventually receives a non-error response. A CP system may reject or delay operations on the minority side. An AP system may accept them and reconcile divergent state later.

This is not “choose two of three” during normal operation. Network partitions are conditions, not optional features, and many systems choose differently per operation. A catalog may serve stale descriptions while inventory reservation requires a leader. Even during a partition, bounded waiting turns a latency decision into an error response; whether that is acceptable belongs to the API contract.

PACELC adds the ordinary case: if Partition, choose Availability or Consistency; Else, choose Latency or Consistency. Synchronous cross-region replication can preserve a stronger order but puts network distance on the write path. Local reads and asynchronous replication reduce latency but permit staleness. Hardware does not repeal that tradeoff, although careful placement, batching, and leader leases can move its practical boundary.

CAP also does not decide conflict semantics, durability, transaction isolation, or staleness bounds. A system can be available yet lose acknowledged writes after correlated failures. It can be linearizable for one key but not provide an atomic snapshot across keys. Treat CAP and PACELC as questions that expose choices, not badges attached to a database product.

Choose and test from product invariants #

Start with a workflow, its harm, and its recovery path. Authentication revocation, uniqueness claims, inventory decrements, and money movement often justify coordination because double action is expensive or irreversible. Search indexes, presence indicators, analytics, and recommendation feeds usually tolerate bounded staleness. A profile edit may need only read-your-writes; collaborative editing may need causal ordering plus a domain-specific merge.

Write the contract in observable terms: “After checkout returns success, every authorization decision sees the reservation,” or “Search may lag publication by 30 seconds.” State the scope, including key, tenant, region, and session. Define behavior when the guarantee cannot be met: fail closed, return stale data with an age marker, queue work, or degrade a feature. Then choose the weakest model that satisfies the invariant, because stronger coordination consumes latency and failure budget.

Known anomalies make reviews concrete. Stale reads return an older version. Monotonic-read violations move a client backward. Lost updates overwrite concurrent work without detection. Read skew combines values from different logical times. Write skew lets transactions preserve per-row rules while violating a cross-row invariant, usually an isolation problem. Duplicate effects often come from retries rather than replication, but users experience them as one broken consistency promise.

Ordinary unit tests cannot establish a distributed guarantee. Add layers suited to the risk:

• Model-based tests generate operation histories and check them against a small reference state machine.
• Deterministic simulation varies message order, delay, crash, restart, and clock behavior while preserving replayable seeds.
• Fault-injection tests partition replicas, pause leaders, drop acknowledgements, and move clients between regions.
• Linearizability checkers search a recorded concurrent history for a legal real-time-respecting order.
• Product tests assert session tokens, idempotency keys, conflict responses, and stale-read indicators at API boundaries.

Record invocation time, completion time, client or session ID, operation, input, output, replica or leader, and version metadata. Logs that contain only final values cannot reconstruct ordering. Test ambiguous outcomes deliberately: disconnect after the server commits but before the response arrives, then verify that retrying the same command returns the original result instead of applying it twice.

Production observability should measure replication lag distributions, quorum failures, leader changes, conflict rates, session-token waits, and the age of served data. Averages hide the users routed to a slow replica. Alerts should connect technical symptoms to contract thresholds: a 45-second search lag is harmless under a one-minute objective and severe under a five-second one.

Takeaways #

Linearizability gives operations a single legal order that respects real time. Sequential consistency preserves client program order without that cross-client real-time promise. Causal consistency orders causes before effects, while session guarantees preserve selected expectations for one user’s path. Eventual consistency guarantees convergence only after updates stop and delivery succeeds; it does not define freshness or business-correct conflict resolution.

Quorums are ingredients, not conclusions. Their guarantees depend on versioning, read repair, membership, failure assumptions, and the exact protocol. CAP explains choices during partitions; PACELC reminds us that latency versus coordination remains when the network is healthy.

The practical method begins with product invariants and explicit failure behavior. Apply strong coordination where duplicate or reordered action causes unacceptable harm, use weaker models where stale information is recoverable, and test the actual histories produced under faults. A consistency model earns its value only when engineers can state what users will observe on the worst day, not just what the database does in a clean benchmark.