Consistency Models: Linearizable to Eventual

What you'll learn: By the end of this lesson you will be able to define a consistency model as the set of histories a system may produce, state the exact promise of linearizable, sequential, causal and eventual consistency using the original papers' wording, name the four session guarantees and the anomaly each removes, read Jepsen's availability classes, check a small history with a short Java program, and assign a model to each feature of a product.

A company keeps its price list on one whiteboard in the middle of the office. Anyone who walks past reads the current prices, and when someone rubs out a price and writes a new one, every later reader sees the new one. Now the company opens two more offices and pins a photocopy of the whiteboard in each. Updating the original no longer updates the copies at once. A clerk in the second office may read yesterday's price, and a customer who is told two different prices by two clerks will not be amused.

The whiteboard is one promise, and every photocopy scheme is a weaker promise with its own list of surprises. Which surprises you can live with, for which prices, is what a consistency model describes. The overview, CAP, PACELC and consistency models, gives a paragraph per model and CAP Theorem and PACELC explains why a partition forces a choice. This lesson is the dedicated treatment of the models: what each forbids, where the definitions come from, what it costs, and how to choose.

Read from the primary sources and checked on 2026-11-08: Herlihy and Wing (1990), Lamport (1979), Terry et al. (1994), Vogels (2008), Kleppmann (2015) and the Jepsen consistency pages. No product versions are involved.

The core idea

A consistency model is a contract about histories. A history is the list of operations clients performed, with when each one started, when it finished and what it returned. The model says which histories are allowed. A stronger model allows fewer histories, so it has fewer surprises and costs more coordination. Jepsen puts it this way: a consistency model is a safety property that declares what a system can do.

Three kinds of example run through the lesson, each labelled:

• Minimal example: a 100-line Java program that checks small histories against four models and prints which ones they satisfy.
• Realistic example: ShopStream's order confirmation page, read from a replica that is a moment behind the primary.
• Failure example: a shopper who refreshes the order page and watches the status go backwards.

Histories: the language of the models

An operation has an invocation (the client sends it) and a response (the client hears back). Two operations are concurrent when their intervals overlap. If operation A responds before operation B is invoked, A precedes B in real time.

A single-copy register with no concurrency is easy: a read returns the latest write. Concurrency and replication are what make it hard, because there is more than one defensible answer to "what should this read return?". Each consistency model picks which answers are acceptable. The diagram shows the situation that separates the strong models from the rest.

Figure 1. The stale read that separates strong from weak models. How to read this: time runs downward. The write completes before the read starts, yet the read returns the old value because the replication message is still in flight. Linearizability forbids this history. Sequential, causal and eventual consistency all allow it.

Linearizability: the single-copy illusion

Maurice Herlihy and Jeannette Wing defined it in 1990. Their abstract says linearizability "provides the illusion that each operation applied by concurrent processes takes effect instantaneously at some point between its invocation and its response". A history is linearizable when some legal sequential order of its operations also respects real-time precedence: if A finished before B began, A comes first. Jepsen states the same rule.

The consequences are concrete:

• A read that starts after a write has completed must return that write or a later one. Figure 1 breaks this.
• Concurrent operations may be ordered either way, so a read that overlaps a write may return the old or the new value.
• Once any reader has seen the new value, every read that begins afterwards must see it too. There is no going back.

Two properties from the paper matter in design. Locality: a system is linearizable if each individual object is, so objects can be built and checked independently; sequential consistency and serializability are not local. Nonblocking: the model itself never forces a process with a pending call to a total operation to wait; blocking comes from implementations. Jepsen adds the scope warning: linearizability is a single-object model, and "an object" may be a key, a table or a database. For guarantees across objects it points to strict serializability, which Herlihy and Wing describe as the transaction version, with linearizability as the case where each transaction is one operation on one object.

The price is availability. Jepsen classes linearizability as neither totally available nor sticky available: during a partition, some or all nodes cannot make progress. That is the CAP result seen from the model's side (CAP lesson). Systems that offer it route operations on a key through a single leader or a consensus group (consensus and leader election). The common failure is assuming a database is linearizable when it is not. Kleppmann's examples: reads from asynchronous followers in single-leader replication are not linearizable, ZooKeeper reads are not linearizable by default, and a Dynamo-style store should not be assumed linearizable just because it uses quorum reads and writes (R + W > N).

Use it where a stale answer costs money or breaks a uniqueness rule: balances, stock that must not oversell, unique usernames, leader election.

Sequential consistency: one order, no clock

Leslie Lamport defined it in a two-page note in 1979, for multiprocessor memory. A multiprocessor is sequentially consistent when "the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program."

Both models want one total order that every process agrees on. Sequential consistency only requires that order to respect each process's own program order, not real time. So Figure 1 is allowed: "B reads 0, then A writes 1" is a legal total order that keeps each client's own order. Herlihy and Wing make the same point: it is weaker because it does not require the original history's precedence order to be preserved.

Lamport's note also explains why the order matters. In a two-process mutual-exclusion protocol, each process sets its own flag and then reads the other's. If a processor may read before it writes, both can enter the critical section. That gives his requirement R1: each processor issues memory requests in the order specified by its program. He then shows R1 alone is not enough, because with several memory modules a read to one can overtake a write to another, so he adds R2: requests to one memory module are served from a single FIFO queue. Together they make the whole machine sequentially consistent if each processor is sequential.

Two limits. It is not local: Herlihy and Wing give a two-queue history where each queue's sub-history is sequentially consistent but the combined history is not. And Jepsen classes it, like linearizability, as neither totally available nor sticky available. Jepsen's intuition: a process may read stale state, but once it has observed some operation it cannot observe anything earlier. In product design the difference from linearizability rarely decides anything, but vendor pages often confuse the two.

Causal consistency: causes before effects

Causal consistency drops the demand for one global order and keeps only the part that users can notice. If one operation could have influenced another, every process must see them in that order. Jepsen: causally related operations should appear in the same order on all processes; processes may disagree on the order of causally independent operations. The "could have influenced" relation is Lamport's happens-before: operations by the same process are ordered, and an operation that reads a value is after the write it read (the IDs, clocks and ordering lesson covers the clocks that track it).

Figure 2. The anomaly causal consistency exists to prevent. How to read this: Bob's reply was caused by what he read, so it must not become visible anywhere before the question. A causal system holds the reply back until its cause has arrived, or delivers both together. Two unrelated posts may still appear in either order to different readers.

This is the first model on the way down that survives a partition, with a condition. Jepsen classes causal consistency as sticky available: clients connected to a non-faulty node can keep making progress, as long as each client keeps talking to the same server. The cost is bookkeeping. The system tracks dependencies (a version vector or a dependency list per operation) and delays making an operation visible until what it depends on is visible.

Session guarantees: the practical middle

Terry, Demers, Petersen, Spreitzer, Theimer and Welch worked on a replicated store for mobile users at Xerox PARC (the Bayou project). A mobile client could write to one server and read from another that had not yet heard of the write. Their 1994 paper proposes four guarantees, each scoped to one client's session, designed to sit on top of a weakly consistent system. Its definition of the first: if a read follows a write in a session and is performed at server S at time t, the write is included in S's database at t.

The mechanism is simple. Each write gets a unique identifier, and the client keeps a record of the writes it has read and written (compacted to version vectors). Before using a server, the client checks that the server's version vector covers what the session needs; if not, it picks another server or waits. The paper is open about the price: a guarantee can reduce availability, because the client may have to find a server that is current enough.

Jepsen's availability classes for these differ. Read your writes is sticky available. Monotonic reads, monotonic writes and writes follow reads are classed as totally available. PRAM, which Jepsen states is exactly equivalent to read your writes, monotonic writes and monotonic reads together, is sticky available. Jepsen describes causal consistency as stricter than PRAM, also enforcing writes follow reads, so it sits above all four in strength.

Figure 3. Read your writes without making every read strong. How to read this: only this client's reads are constrained by its token. Other clients keep reading from replicas, so the extra load falls on the primary only for readers who have just written.

Eventual consistency: the weakest useful promise

Werner Vogels' definition: if no new updates are made, eventually all accesses return the last updated value. The period before that is the inconsistency window, which depends on communication delays, load and the number of replicas. Terry et al. say the goal relies on two properties: total propagation (every write reaches every replica) and consistent ordering (replicas apply writes in an order that leads to the same state).

Two things are easy to miss. First, it is a statement about where the system ends up, not about the path. Nothing in it forbids a stale read, a read that goes backwards, or a reply before its post. That is why it is combined with the session guarantees in practice. Second, "converge" needs a rule when two replicas accepted conflicting writes: last-write-wins, merging, or keeping both versions. The CAP lesson shows a cart union merge and its cost. Vogels' everyday example is DNS, the most popular system he names that implements eventual consistency.

The ladder, and what each rung costs

Figure 4. The models as a ladder. How to read this: an arrow means "implies", so everything below a model is also guaranteed by it. The boxes are Jepsen's availability classes: stronger models cost availability during a partition. Eventual consistency stands apart because it constrains the end state, not what a read may return on the way.

The ladder is a partial order, not a line, and many databases let you choose per request, so ask what a particular operation guarantees, not which label a product wears. Kleppmann's complaint about "CP" and "AP" labels is the same point: one system can have operations with different consistency characteristics, and many systems fit neither bucket.

Minimal example: checking histories by brute force

The way to make these definitions concrete is to check histories mechanically. The program below takes small histories of reads and writes on registers and tries to find a total order that explains them. With the real-time rule on it checks linearizability. With it off, only each process's own order must hold, which is sequential consistency. It also checks two session guarantees directly, treating values as versions (a bigger number is newer). It is a teaching tool: the search is exponential in the worst case, and it is not how a production checker such as Jepsen's works.

import java.util.*;

public class HistoryCheck {
    // One finished operation: who, read or write, which register, value, start and end time.
    record Op(String proc, boolean write, String key, int value, int start, int end) {
        static Op w(String p, String k, int v, int s, int e) { return new Op(p, true, k, v, s, e); }
        static Op r(String p, String k, int v, int s, int e) { return new Op(p, false, k, v, s, e); }
    }

    // Is there a total order of all operations that respects the register semantics,
    // each process's own order, and (if realTime) "A ended before B began => A before B"?
    static boolean exists(List<Op> ops, boolean realTime) {
        return place(ops, new boolean[ops.size()], new HashMap<>(), realTime, 0);
    }

    static boolean place(List<Op> ops, boolean[] done, Map<String, Integer> state, boolean rt, int placed) {
        if (placed == ops.size()) return true;
        for (int i = 0; i < ops.size(); i++) {
            if (done[i] || !mustComeFirstAreDone(ops, done, i, rt)) continue;
            Op o = ops.get(i);
            Integer old = state.get(o.key());
            if (!o.write() && o.value() != (old == null ? 0 : old)) continue; // a read must return the current value
            if (o.write()) state.put(o.key(), o.value());
            done[i] = true;
            if (place(ops, done, state, rt, placed + 1)) return true;
            done[i] = false;
            if (o.write()) { if (old == null) state.remove(o.key()); else state.put(o.key(), old); }
        }
        return false;
    }

    static boolean mustComeFirstAreDone(List<Op> ops, boolean[] done, int i, boolean rt) {
        Op o = ops.get(i);
        for (int j = 0; j < ops.size(); j++) {
            if (j == i || done[j]) continue;
            Op p = ops.get(j);
            boolean before = (p.proc().equals(o.proc()) && p.start() < o.start()) || (rt && p.end() < o.start());
            if (before) return false;
        }
        return true;
    }

    // Session checks (values are versions, so a bigger value is newer).
    static boolean readYourWrites(List<Op> ops) {
        Map<String, Integer> written = new HashMap<>();
        for (Op o : sorted(ops)) {
            String k = o.proc() + "/" + o.key();
            if (o.write()) written.merge(k, o.value(), Math::max);
            else if (o.value() < written.getOrDefault(k, 0)) return false;
        }
        return true;
    }

    static boolean monotonicReads(List<Op> ops) {
        Map<String, Integer> seen = new HashMap<>();
        for (Op o : sorted(ops)) {
            if (o.write()) continue;
            String k = o.proc() + "/" + o.key();
            if (o.value() < seen.getOrDefault(k, 0)) return false;
            seen.put(k, o.value());
        }
        return true;
    }

    static List<Op> sorted(List<Op> ops) {
        return ops.stream().sorted(Comparator.comparingInt(Op::start)).toList();
    }

    static void show(String name, List<Op> ops) {
        System.out.printf("%-34s %-13s %-11s %-4s %s%n", name,
                yes(exists(ops, true)), yes(exists(ops, false)), yes(readYourWrites(ops)), yes(monotonicReads(ops)));
    }

    static String yes(boolean b) { return b ? "yes" : "NO"; }

    public static void main(String[] args) {
        System.out.printf("%-34s %-13s %-11s %-4s %s%n", "history", "linearizable", "sequential", "RYW", "MR");
        System.out.println("-".repeat(70));
        show("H1 read overlaps the write, old", List.of(
                Op.w("A", "x", 1, 0, 30), Op.r("B", "x", 0, 10, 20)));
        show("H2 read after the write, old", List.of(
                Op.w("A", "x", 1, 0, 10), Op.r("B", "x", 0, 20, 30)));
        show("H3 two readers disagree in order", List.of(
                Op.w("A", "x", 1, 0, 100), Op.r("B", "x", 1, 10, 20), Op.r("C", "x", 0, 30, 40)));
        show("H4 one reader goes backwards", List.of(
                Op.w("A", "x", 1, 0, 100), Op.r("B", "x", 1, 10, 20), Op.r("B", "x", 0, 30, 40)));
        show("H5 writer misses its own write", List.of(
                Op.w("A", "x", 1, 0, 10), Op.r("A", "x", 0, 20, 30)));
        show("H6 Lamport's flags, both read 0", List.of(
                Op.w("P1", "a", 1, 0, 10), Op.r("P1", "b", 0, 20, 30),
                Op.w("P2", "b", 1, 5, 15), Op.r("P2", "a", 0, 25, 35)));
    }
}

Run it with java HistoryCheck.java (Java 25 or later; the single-file launcher compiles it in memory). Expected output (identical when re-run under JDK 25 on 2026-11-08):

history                            linearizable  sequential  RYW  MR
----------------------------------------------------------------------
H1 read overlaps the write, old    yes           yes         yes  yes
H2 read after the write, old       NO            yes         yes  yes
H3 two readers disagree in order   NO            yes         yes  yes
H4 one reader goes backwards       NO            NO          yes  NO
H5 writer misses its own write     NO            NO          NO   yes
H6 Lamport's flags, both read 0    NO            NO          yes  yes

How to read the table, row by row:

The checker cannot show causal consistency, which needs the read-from relation; the point of the table is how the models separate. Break it: change H2's read to return 1 and every column becomes "yes". Then change the true in exists(ops, true) to false in show: the linearizable column now equals the sequential one without touching a single history, which is the whole difference between the first two models. Stretch: add a history with two writers and two readers in which the readers see two independent writes in opposite orders, and find out which of the four columns reject it.

Misconceptions, corrected

The other side of this topic

The browser meets these models as optimistic updates: the interface shows an action as done before the server has confirmed it, and must be able to roll back or reconcile if the server answers differently. The Frontend System Design track plans a lesson on optimistic updates and rollback (not published yet, so there is no link). The back-end rule that makes the front end's job possible is to say per operation which guarantee it has, and to return an error or a version the interface can act on.

In practice: the order confirmation that says "not found"

This is the realistic example. It is an educational scenario on the course's running example, ShopStream, and nothing in it describes a real company. Every figure is illustrative.

This is a realistic scenario, not a case history.

The situation

ShopStream's Stage 2 added read replicas to take browsing load off the primary database (scale reads). At the course's illustrative peak of about 58 checkouts per second, a shopper pays and the browser is sent to the confirmation page. The confirmation page reads the order from a replica. The replica is a few hundred milliseconds behind, an illustrative figure, so a small share of shoppers see "order not found" for a moment, press the button again and place a duplicate order. The team asks whether to send every read to the primary.

Starting architecture

Figure 5. The design under discussion. How to read this: everything starts at the order API. The top path goes to the primary and is always fresh. The bottom path goes to replicas that trail the primary by a replication delay, so reads there may be stale.

Options considered

The decision

Option B, scoped by feature. The point is to give each read the weakest guarantee that its user cannot notice, not to pick one model for the product:

The confirmation page stops failing because the token says "version 7 or later", and the read goes to the primary when the replica is at version 5. Everyone else keeps reading replicas.

Rollout and verification

A rollout would first log, for a sample of reads, the token held and the version the replica returned, to count how often a replica was behind. Verification is a test that writes an order, reads it through the router with its token while a replica is held back, and asserts the order is returned, plus a test that two consecutive reads with a rising token never return a lower version. Metrics: the fraction of token reads that fell back to the primary, replica lag, and duplicate-order attempts.

The 2 a.m. failure

The page reads: primary CPU high, fallback rate near 100 percent. A nightly batch job loaded a replica, replication fell behind, and every token read went to the primary: Option A arriving by the back door. The checks: lag per replica, the fallback ratio, the primary's connection count. The mitigation is to let a read wait a bounded time for a replica before falling back, to cap the fallback rate and show an honest "your order is being confirmed" page, and to move the batch job to its own replica. The lasting fix is to alert on replica lag and size the primary for the fallback rate you accept.

Failure example: the status that goes backwards

The failure example is the monotonic reads anomaly. A shopper tracks an order. The load balancer sends each refresh to a different replica, and the replicas are at different points.

Figure 6. A client that sees time go backwards. How to read this: each read is individually fine, because both values were true at some moment. The violation is in the sequence one client sees. This is row H4 of the checker: no real-time reasoning is needed to call it wrong.

What breaks: support tickets ("the app says my order is packed again") and clients that act on the first value. Detection: log the status version each session sees and alert on a decrease. Prevention: carry the last version seen in the session and have the router refuse an older replica, or pin the session to one replica. Both are the session guarantees from Terry et al.

Architect's notes

• Name the guarantee per operation. A table with one row per read and write beats "we use strong consistency".
• Ask what a stale answer costs. Money and uniqueness get the strongest model, noticeable oddities a session guarantee, the rest eventual.
• Scope it to one object. If two keys must change together, you need a transaction or a single owner.
• Read the docs for the operation, not the brand. A store is rarely "strong" or "eventual" in general.
• Treat the session token as a first-class thing. It gives one client linearizable-looking behaviour on weak copies.

Common mistakes

• Confusing sequential with linearizable. The first has no real-time rule.
• Calling a replicated database "strongly consistent" without checking where reads go.
• Using eventual consistency for data a user just wrote and will read straight back.
• Ordering causal events by wall-clock time. Clocks drift; use version or dependency information.
• Promising monotonic reads while round-robining across replicas.

Key takeaways

• A consistency model is the set of histories a system may produce; stronger models allow fewer.
• Linearizable: each operation appears instantaneous between invocation and response, respecting real time; per object; costs availability in a partition.
• Sequential: one total order plus each process's program order, ignoring real time.
• Causal: causes before effects; sticky available.
• The four session guarantees remove the anomalies one client notices, typically with a token.
• Eventual promises only convergence once writes stop; pair it with session guarantees and a conflict rule.
• Choose per feature: strongest for money and uniqueness, session guarantees for what users notice, eventual elsewhere.

Practice exercises

Exercise 1 (30 min). Without running the program, predict the four columns for a history where A writes x=1 and then x=2, and B reads x=2 and then x=1. Add it and compare.

Exercise 2 (45 min). For ten features of a food-delivery app, write the cost of a stale read and assign a model; mark each one that needs a token.

Exercise 3 (1 hour). Extend HistoryCheck with a writes-follow-reads check and write one passing and one failing history.

Exercise 4 (1 hour). Design the version token for the order confirmation page: its contents, where it lives, how a replica proves it is current enough, and what happens when it is lost.

Exercise 5 (2 hours). For a Dynamo-style store with N = 3, W = 2, R = 2 (see the CAP lesson), construct a history that is stale despite R + W > N and say which model it violates.

Related reading

• CAP, PACELC and Consistency Models: the overview, with quorums and the feature table.
• CAP Theorem and PACELC: why a partition forces a choice, and the quorum lab.
• Replication: leaders, followers and replication lag.
• Consensus and Leader Election: how systems get linearizability.
• IDs, Clocks and Ordering: happens-before, logical and vector clocks.
• Distributed Transactions: guarantees across several objects.
• ShopStream Stage 2: the read replicas in the realistic example.

Official documentation

• Herlihy and Wing, Linearizability: A Correctness Condition for Concurrent Objects (ACM TOPLAS 12(3), July 1990): the definition, locality and the comparison with sequential consistency and serializability.
• Lamport, How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs (IEEE Transactions on Computers, September 1979): sequential consistency.
• Terry et al., Session Guarantees for Weakly Consistent Replicated Data (PDIS 1994): the four session guarantees.
• Jepsen, Consistency Models: definitions and availability classes; see also the pages for linearizable, sequential and causal.
• Vogels, Eventually Consistent (2008): eventual and session consistency from an operator's view.
• Kleppmann, Please stop calling databases CP or AP (2015).