The Project | About Us | Contribute | Donations | License

HOME

Module 2 ended on an awkward scene: Anna reserves the last aged-cheese from Montblanc Dairy, inventory deducts it, and during the half second it takes stock.updated to reach catalog, Mark is still looking at a product page for a cheese that no longer exists. Nobody made a programming mistake; the piece of data "units of aged cheese" simply lives in more than one place now, and those places do not agree instantly. The question that opens this module is what exactly it means for such a system to be "consistent", because the word on its own says nothing: it has a dozen different meanings, each with its own cost and its own set of permitted anomalies.

This lesson builds that vocabulary. We will see that a consistency model is a contract between the data store and the program that uses it, and we will walk down the hierarchy of contracts from the strongest (linearizability, and why the ideal of "strict consistency" is physically unachievable) to the weakest (eventual consistency), passing through the serializability of databases, sequential consistency and causal consistency, which ties in directly with happens-before and the vector clocks of 01-05. We will then switch viewpoint and look at the guarantees that matter to one particular client, Anna, when she edits her delivery address and watches it disappear. Everything will be made visible with a Python simulation of the inv-bcn and inv-vlc replicas with delayed propagation. What can be promised when the network splits (CAP), how nodes reach agreement (consensus) and how data is physically copied (replication) are the subject of the following lessons; here we only define precisely what is being promised.

A consistency model is a contract
The hierarchy of models
Linearizability and the unachievable ideal of strict consistency
Checking the linearizability of a history by hand (and in Python)
Serializability: similar, but not the same thing
Sequential consistency
Causal consistency: happens-before applied to data
Eventual consistency and strong eventual consistency (CRDTs)
Client-centric models: what Anna expects from her session
Simulation: inv-bcn and inv-vlc with delayed propagation
Comparison table: model, guarantee, cost and use at Kilometre Zero
Common mistakes and tips
Exercises
Conclusion

A consistency model is a contract

When the Kilometre Zero monolith had a single PostgreSQL database, the programmer never wondered "which version of the stock am I reading?": there was one, the latest. Once the data is distributed, several copies appear that may differ at any given moment, and the store has to decide what it promises about those copies to whoever reads and writes. That promise is the consistency model.

Formally, a consistency model is the set of histories (sequences of operations together with their results) that the store considers valid. If the program observes a history the model does not allow, the store has broken the contract; if it observes any other history, however odd it may look, the store has kept it. Two practical consequences follow:

The contract has two sides. The store promises not to produce certain histories, and the program undertakes to work correctly with any permitted history. If catalog assumes it always reads the latest stock but the store only guarantees eventual consistency, the bug is not in the store.
Stronger is not simply better. Every additional guarantee costs latency, availability or both (we will quantify this in 03-02). Choosing a model means choosing which anomalies you are willing to tolerate in exchange for what.

In 01-05 we learned to reason about the order of events without a global clock; consistency models are that same idea applied to reads and writes: each model imposes a different kind of order on the operations.

The hierarchy of models

Models are ordered by strength: one is stronger than another if it allows a subset of the other's histories. The diagram shows the hierarchy we will use in this course (simplified; the real one has dozens of intermediate models):

flowchart TB
    ST["Strict consistency<br/>(physical ideal: perfect global clock)"]
    L["Linearizability<br/>(total order respecting real time)"]
    SS["Strict serializability<br/>(transactions + real time)"]
    SR["Serializability<br/>(transactions in some total order)"]
    SQ["Sequential consistency<br/>(total order respecting each process's order)"]
    C["Causal consistency<br/>(only causally related operations are ordered)"]
    CL["Client-centric models<br/>read-your-writes, monotonic reads..."]
    EV["Eventual consistency<br/>(replicas converge... some day)"]
    ST -.-> L
    L --> SQ
    SS --> L
    SS --> SR
    SQ --> C
    C --> CL
    CL --> EV
    style ST stroke-dasharray: 5 5

The arrows run from stronger to weaker. The left-hand column (strict → linearizable → sequential → causal → eventual) is about individual operations on objects; the right-hand branch (serializability) is about transactions that group several operations, and the two meet at strict serializability. We will walk down the hierarchy from top to bottom.

Linearizability and the unachievable ideal of strict consistency

Strict consistency

The strongest model imaginable says: "every read returns the value of the most recent write according to a global clock". It is exactly what a variable offers in a single-threaded program, and it is what we intuitively expect. But in 01-05 we saw that there is no global clock: NTP synchronises with an error of milliseconds, and "the most recent write" is not defined for two writes that happen 100 microseconds apart in Girona and Valencia, because no information can travel between them in that time. Strict consistency is a physical ideal, useful as a reference point, but no distributed system can implement it or verify it. That is why it appears with a dashed line in the diagram.

Linearizability

Linearizability (Herlihy and Wing, 1990) is the achievable version of that ideal. It starts from the observation that every operation in a real system is not instantaneous: it has a start time (the client sends the request) and an end time (it receives the response). Linearizability requires that:

There is a total order of all operations.
In that order, every read returns the value of the immediately preceding write (the sequential specification of the object: for a register, "a read returns whatever was written last").
The order respects real time: if operation A finished before operation B started, A comes before B in the order.

The intuitive consequence is that each operation appears to take effect atomically at some instant between its start and its end, the so-called linearization point. Two operations that overlap in time may be ordered either way (that is the freedom that makes the model achievable), but once an operation has finished, its effect is visible to everybody. At Kilometre Zero, linearizability is what makes reserving the last cheese meaningful: if Anna's ReserveStock returns "confirmed", any later query by anyone, from any replica, must see 0 units. Not even inv-vlc may go on saying 1.

Linearizability is composable: if every object is linearizable on its own, the system as a whole is too. This is not true of sequential consistency or of serializability, and it is one of the reasons for its popularity as the guarantee offered by coordination systems (etcd, ZooKeeper, which we will meet in 03-03).

Checking the linearizability of a history by hand (and in Python)

A history is a list of operations, each with a process, a kind, an argument or result, and a real-time interval. Checking whether it is linearizable means looking for a total order that meets the three conditions. Let us take the stock of aged-cheese, which starts at 1:

Operation	Client	Start (ms)	End (ms)	Result
A	Anna: write stock = 0 (reservation)	0	10	ok
B	Mark: read stock	12	15	1
C	Lucy: read stock	5	20	0

By hand. A finished at 10 and B started at 12, so A must come before B. But B read 1, that is, the value from before A. No valid order exists: the history is not linearizable. It is exactly what happened to Mark at the close of 02-05. Look at C: it overlaps with A (5-20 versus 0-10), so it may go before or after A; it read 0, so it must go after. That is legal. Had B read 0, the order A, C, B (or A, B, C) would be valid and the history would be linearizable.

In Python. For small histories the check can be done by brute force: generate every permutation, discard those that violate real time and check the register specification against the rest. It is no use for real histories (the problem is NP-complete, and tools such as Jepsen/Knossos use far smarter algorithms), but it makes the definition tangible:

# km0/simulations/linearizability.py
from dataclasses import dataclass
from itertools import permutations


@dataclass(frozen=True)
class Op:
    name: str
    client: str
    kind: str          # "write" or "read"
    value: int         # what it writes, or what it read
    start: int
    end: int


def respects_real_time(order: list[Op]) -> bool:
    """If A finished before B started, A must come before B."""
    for i, a in enumerate(order):
        for b in order[i + 1:]:
            if b.end < a.start:       # b finished before a started, yet comes later
                return False
    return True


def satisfies_specification(order: list[Op], initial_value: int) -> bool:
    """A register: every read returns the last write before it in the order."""
    current = initial_value
    for op in order:
        if op.kind == "write":
            current = op.value
        elif op.value != current:
            return False
    return True


def is_linearizable(history: list[Op], initial_value: int) -> list[Op] | None:
    """Returns a valid linearization order, or None if there is none."""
    for order in permutations(history):
        order = list(order)
        if respects_real_time(order) and satisfies_specification(order, initial_value):
            return order
    return None


if __name__ == "__main__":
    history = [
        Op("A", "Anna", "write", 0, start=0,  end=10),
        Op("B", "Mark", "read",  1, start=12, end=15),
        Op("C", "Lucy", "read",  0, start=5,  end=20),
    ]
    order = is_linearizable(history, initial_value=1)
    print("History 1:", "linearizable" if order else "NOT linearizable",
          [op.name for op in order] if order else "")

    history[1] = Op("B", "Mark", "read", 0, start=12, end=15)   # Mark sees the 0
    order = is_linearizable(history, initial_value=1)
    print("History 2:", "linearizable" if order else "NOT linearizable",
          [op.name for op in order] if order else "")

Output:

History 1: NOT linearizable
History 2: linearizable ['A', 'B', 'C']

A walk through the code for beginners:

Op is an operation with its real-time interval. frozen=True makes it immutable, which lets us use it in permutations without surprises.
respects_real_time checks condition 3 of the definition: it goes through every pair (a before b in the candidate order) and fails if b finished strictly before a started.
satisfies_specification walks the order keeping track of the register's "current" value and checks that every read returns that value. Changing this function would let us check other objects (a queue, a counter).
is_linearizable tries every order. With 3 operations that is 6 permutations; with 10 it would be 3.6 million. It is for understanding, not for production.

Serializability: similar, but not the same thing

Serializability comes from the database world and talks about transactions, not individual operations: a history of transactions is serializable if its outcome equals that of some sequential order of those same transactions. It is the "I" of ACID in its strongest form (we will come back to ACID in 03-05). It is constantly confused with linearizability because both talk about "a total order", but they differ in two respects:

Aspect	Linearizability	Serializability
Unit	One operation on one object	One transaction over several objects
Time constraint	Yes: it respects real time	No: any sequential order will do, even one that contradicts real time
Composition	Composable per object	Not composable
Where you see it	Registers, locks, queues, coordination systems	Relational databases (`SERIALIZABLE` level)

The absence of a time constraint has real consequences. Imagine orders runs transaction T1 (create P-2026-000123) and, after receiving the "commit ok", Lucy runs T2 (list today's orders). A serializable system may legally order T2 before T1 and return Lucy a list without the order, because that sequential order is valid. PostgreSQL with SERIALIZABLE on a single node does not do this in practice, but a serializable distributed database with lagging replicas can.

The combination of the two, strict serializability, requires a sequential order of transactions that also respects real time. It is the strongest guarantee offered in practice (Spanner implements it with TrueTime, mentioned in 01-05; CockroachDB and FoundationDB aim for it too) and the most expensive. When we talk about the "C" of CAP in 03-02, we will mean linearizability; when we talk about transactions in 03-05, serializability.

Sequential consistency

Let us relax linearizability by dropping the real-time constraint and keeping only this one: there is a total order that respects the program order of each process. That is, Anna's operations appear in the order in which Anna issued them, Mark's in Mark's order, but how the two sequences interleave is free, regardless of the clock.

Under sequential consistency, history 1 from section 4 would be valid: the order B, A, C (Mark reads 1, Anna writes 0, Lucy reads 0) respects each process's order (each one performed a single operation) and the register specification. The fact that Mark started reading after Anna had finished does not matter. What sequential consistency forbids are histories in which a process sees its own operations out of order, or in which two processes see other processes' writes in different orders. This is the model offered by multi-core CPUs with some restrictions (the "memory model" of Java or C++ is built on this idea) and, in distributed systems, by a store with a single leader that orders all writes and replicas that apply them in that same order, albeit with a delay.

At Kilometre Zero, sequential consistency is enough for the position history of van-3: everyone looking at the map will see the van drive down the same streets in the same order, even if one viewer sees it a second behind another.

Causal consistency: happens-before applied to data

Sequential consistency still demands a total order, and that forces all nodes to agree on how to interleave operations that have nothing to do with each other. Causal consistency relaxes precisely that: it only requires the order of causally related operations to be respected, and leaves concurrent ones in any order, even a different one for different observers.

"Causally related" is exactly the happens-before relation from 01-05, applied to reads and writes:

If a process performs operation A and then B, A → B.
If a process reads a value written by A and then writes B, A → B (the write may have depended on what was read).
Transitivity.

And "concurrent" operations are those not related in either direction, the same ones we detected in 01-05 with VectorStamp.concurrent. This is no coincidence: systems with causal consistency (COPS, Antidote, or MongoDB's causal mode) are implemented with vector clocks or equivalent structures, and a replica only applies a write once it has applied all the writes that causally preceded it.

The canonical example is a conversation. Mark posts a question on Montblanc Dairy's page ("is the aged cheese made with raw milk?") and the dairy replies ("yes, from Friesian cows"). The reply depends causally on the question (the dairy read it before writing). With eventual consistency, Lucy on another replica could see the reply before the question: an absurdity. With causal consistency that is forbidden; but if Anna posts an unrelated question about shipping at the same time, whether Lucy sees it before or after Mark's is irrelevant and the system spends nothing on deciding it.

Causal consistency is the strongest model that can be offered without sacrificing availability during a network partition, a result that makes it the favourite sweet spot of academic research and that will give meaning to the discussion in 03-02.

Eventual consistency and strong eventual consistency (CRDTs)

At the weak end sits eventual consistency: if writes stop arriving, all replicas will end up holding the same value. It does not say when ("eventually" may be a millisecond or an hour), it does not say what you read in the meantime, and it does not say what the final value will be if there were concurrent writes. It is more a convergence (or liveness) property than a consistency model in the sense of section 1: almost any history is valid while activity continues. Its virtue is that it can always be offered, over any network and with any latency, which is why it is the default model of DNS, of caches and of most "AP" stores (03-02).

The trouble with plain eventual consistency is reconciliation: when two replicas have accepted concurrent writes, somebody has to decide the final value, and the most common strategy (last-write-wins) silently loses data, as we will see in stark terms in 03-02. Strong eventual consistency (Shapiro et al., 2011) removes that decision: it requires that two replicas which have received the same set of updates, in any order, be in the same state. No reconciliation is needed because the data type itself is designed so that merging is deterministic. Those types are CRDTs (Conflict-free Replicated Data Types).

The simplest CRDT is the grow-only counter, the G-Counter: each replica keeps its own count, the total value is the sum, and merging two states means taking the component-wise maximum (an increment is never lost because each replica only ever raises its own slot):

# km0/simulations/gcounter.py
class GCounter:
    """Replicated grow-only counter (state-based CRDT)."""

    def __init__(self, replicas: list[str]):
        self.counts = {r: 0 for r in replicas}

    def increment(self, replica: str, n: int = 1) -> None:
        self.counts[replica] += n             # each replica only touches its own slot

    def value(self) -> int:
        return sum(self.counts.values())

    def merge(self, other: "GCounter") -> None:
        for r in self.counts:
            self.counts[r] = max(self.counts[r], other.counts[r])

    def __repr__(self) -> str:
        return f"GCounter({self.counts}, total={self.value()})"


if __name__ == "__main__":
    replicas = ["inv-bcn", "inv-vlc"]
    # Units of aged-cheese sold during "Artisan Cheese Week",
    # counted locally at each replica with no coordination.
    bcn = GCounter(replicas)
    vlc = GCounter(replicas)
    bcn.increment("inv-bcn", 3)        # 3 sales in Barcelona
    vlc.increment("inv-vlc", 2)        # 2 in Valencia, concurrently
    print("before merging:", bcn, vlc)

    # Merge in both directions (the order does not matter: the operation is
    # commutative, associative and idempotent)
    bcn_copy = GCounter(replicas); bcn_copy.counts = dict(bcn.counts)
    bcn.merge(vlc)
    vlc.merge(bcn_copy)
    print("after merging:", bcn, vlc)
    bcn.merge(vlc)                     # merging again changes nothing
    print("repeated merge:", bcn)

Output:

before merging: GCounter({'inv-bcn': 3, 'inv-vlc': 0}, total=3) GCounter({'inv-bcn': 0, 'inv-vlc': 2}, total=2)
after merging: GCounter({'inv-bcn': 3, 'inv-vlc': 2}, total=5) GCounter({'inv-bcn': 3, 'inv-vlc': 2}, total=5)
repeated merge: GCounter({'inv-bcn': 3, 'inv-vlc': 2}, total=5)

The key lies in merge: max is commutative (it does not matter who merges into whom), associative (it does not matter in what order three states arrive) and idempotent (merging twice does not double anything). With those three properties, propagation can be as sloppy as you like (duplicates, reordering, delays) and the replicas still converge. There are CRDTs for sets (G-Set, OR-Set), registers (LWW-Register, MV-Register), maps and collaborative text, and we will use them in 03-04 as a conflict resolution strategy in multi-leader replication.

What a CRDT cannot do is maintain a global invariant such as "stock never drops below zero": a replicated PN counter (increments and decrements) would let inv-bcn and inv-vlc each deduct the last unit, and the merged total would be -1. Counting visits to the pink-tomato page or units sold in a campaign is a CRDT use case; reserving the last unit is not. That difference between "data that adds up" and "data that is contended" is what will guide the decisions in 03-02.

Client-centric models: what Anna expects from her session

The models above describe the system from the outside, for all clients at once. But many of the anomalies that really annoy a user concern their own session, and there is a set of guarantees, formulated by Terry et al. for the Bayou system in 1994, that can be offered cheaply even on top of eventual consistency. All four can be seen with Anna editing her delivery address on the website, with her profile replicated on two nodes and delayed propagation:

Guarantee	What it promises	Anomaly it prevents	Scene with Anna
Read-your-writes	After writing a value, the same client never reads an earlier one	"I saved it and it vanished"	Anna changes her address from `Carrer Major 12, Girona` to `Passeig de Gràcia 5, Barcelona`, clicks save, reloads the page and sees the Girona one because the reload landed on the lagging replica
Monotonic reads	Once a client has read a version, it will not later read an older one	"It went back in time"	Anna sees her new address, returns to the page and sees the old one; she reloads, and the new one is back
Monotonic writes	A client's writes are applied on every replica in the order in which the client issued them	"My second change overwrote my first"	Anna changes her address and then her phone number; one replica applies the phone number first (with the old address embedded in the same document) and then the address; another does it the other way round, and the final state differs
Writes-follow-reads	A write issued after reading a value is ordered after the write that produced that value	"The reply before the question"	Anna reads Montblanc Dairy's reply and writes "thanks"; her "thanks" must never be visible on a replica that does not yet show the reply

Together, the four are equivalent to causal consistency restricted to one client (which is why they sit just below it in the diagram in section 2). And all four are obtained with two cheap techniques that we will see in the simulation:

Sticky sessions: each client always talks to the same replica. This trivially gives read-your-writes and monotonic reads, with the drawback that if the replica goes down, the session loses its guarantees (or has to wait for another replica to catch up).
Client-side versions: the client remembers the version (a number, a PostgreSQL LSN, a vector stamp) of the last thing it wrote or read, and every read tells the replica "do not answer me until you have at least this version". It works with any replica and is what MongoDB's causal tokens or the ReadYourWrites option of some client libraries do.

Simulation: `inv-bcn` and `inv-vlc` with delayed propagation

We are going to build two replicas of the stock in Python with a deliberately simple mechanism: every write receives an increasing version number, is applied on the replica that receives it and is propagated to the other one after a delay. A load balancer spreads reads at random between the two. That will be enough to see the anomalies of the previous section appear, and to fix them.

# km0/simulations/lagging_replicas.py
import random
from dataclasses import dataclass, field


@dataclass
class Version:
    value: int
    number: int          # increasing version assigned by the system


@dataclass
class Replica:
    name: str
    data: dict[str, Version] = field(default_factory=dict)
    pending: list[tuple[int, str, Version]] = field(default_factory=list)  # (time, product, version)

    def apply(self, product: str, v: Version) -> None:
        current = self.data.get(product)
        if current is None or v.number > current.number:   # never go back a version
            self.data[product] = v

    def deliver(self, now: int) -> None:
        """Applies the propagations whose arrival time has already passed."""
        ready = [p for p in self.pending if p[0] <= now]
        self.pending = [p for p in self.pending if p[0] > now]
        for _, product, v in sorted(ready):
            self.apply(product, v)

    def read(self, product: str) -> Version:
        return self.data[product]


class System:
    """Two replicas, asynchronous propagation with a delay, random load balancer."""

    def __init__(self, delay_ms: int, seed: int = 7):
        self.replicas = {"inv-bcn": Replica("inv-bcn"), "inv-vlc": Replica("inv-vlc")}
        self.delay = delay_ms
        self.clock = 0
        self.last_version = 0
        self.rng = random.Random(seed)

    def advance(self, ms: int) -> None:
        self.clock += ms
        for r in self.replicas.values():
            r.deliver(self.clock)

    def write(self, replica: str, product: str, value: int) -> Version:
        self.last_version += 1
        v = Version(value, self.last_version)
        self.replicas[replica].apply(product, v)
        for name, other in self.replicas.items():
            if name != replica:
                other.pending.append((self.clock + self.delay, product, v))
        return v

    def random_replica(self) -> Replica:
        return self.rng.choice(list(self.replicas.values()))


def scenario_without_guarantees() -> None:
    print("=== No guarantees: random load balancer, 300 ms propagation ===")
    s = System(delay_ms=300)
    s.write("inv-bcn", "aged-cheese", 3); s.advance(1000)          # initial state propagated
    v = s.write("inv-bcn", "aged-cheese", 2)                       # Anna reserves 1 unit on inv-bcn
    print(f"t={s.clock:4} ms  Anna reserves: stock=2 (version {v.number}) on inv-bcn")
    for _ in range(4):
        s.advance(100)
        r = s.random_replica()
        result = r.read("aged-cheese")
        print(f"t={s.clock:4} ms  Anna reads from {r.name}: stock={result.value} (version {result.number})")


class StickyClient:
    """Always reads from the replica it started with."""
    def __init__(self, s: System, replica: str):
        self.s, self.replica = s, replica
    def read(self, product: str) -> Version:
        return self.s.replicas[self.replica].read(product)


class VersionedClient:
    """Remembers the last version seen and rejects older replicas."""
    def __init__(self, s: System):
        self.s, self.minimum = s, 0
    def write(self, replica: str, product: str, value: int) -> None:
        self.minimum = self.s.write(replica, product, value).number
    def read(self, product: str) -> tuple[str, Version]:
        for r in self.s.rng.sample(list(self.s.replicas.values()), k=2):   # try in random order
            v = r.read(product)
            if v.number >= self.minimum:
                self.minimum = v.number         # monotonic reads: never accept less
                return r.name, v
        raise TimeoutError("no replica has the minimum version yet; retry later")


def scenario_with_guarantees() -> None:
    print("\n=== Sticky session on inv-bcn ===")
    s = System(delay_ms=300)
    s.write("inv-bcn", "aged-cheese", 3); s.advance(1000)
    anna = StickyClient(s, "inv-bcn")
    s.write("inv-bcn", "aged-cheese", 2)
    for _ in range(3):
        s.advance(100)
        print(f"t={s.clock:4} ms  Anna reads from inv-bcn: stock={anna.read('aged-cheese').value}")

    print("\n=== Client with minimum version, random load balancer ===")
    s = System(delay_ms=300)
    s.write("inv-bcn", "aged-cheese", 3); s.advance(1000)
    anna = VersionedClient(s)
    anna.write("inv-bcn", "aged-cheese", 2)
    for _ in range(4):
        s.advance(100)
        try:
            name, v = anna.read("aged-cheese")
            print(f"t={s.clock:4} ms  Anna reads from {name}: stock={v.value} (version {v.number})")
        except TimeoutError as e:
            print(f"t={s.clock:4} ms  {e}")


if __name__ == "__main__":
    scenario_without_guarantees()
    scenario_with_guarantees()

Output (the fixed seed makes the run reproducible):

=== No guarantees: random load balancer, 300 ms propagation ===
t=1000 ms  Anna reserves: stock=2 (version 2) on inv-bcn
t=1100 ms  Anna reads from inv-vlc: stock=3 (version 1)
t=1200 ms  Anna reads from inv-bcn: stock=2 (version 2)
t=1300 ms  Anna reads from inv-vlc: stock=2 (version 2)
t=1400 ms  Anna reads from inv-bcn: stock=2 (version 2)

=== Sticky session on inv-bcn ===
t=1100 ms  Anna reads from inv-bcn: stock=2
t=1200 ms  Anna reads from inv-bcn: stock=2
t=1300 ms  Anna reads from inv-bcn: stock=2

=== Client with minimum version, random load balancer ===
t=1100 ms  Anna reads from inv-bcn: stock=2 (version 2)
t=1200 ms  Anna reads from inv-bcn: stock=2 (version 2)
t=1300 ms  Anna reads from inv-bcn: stock=2 (version 2)
t=1400 ms  Anna reads from inv-vlc: stock=2 (version 2)

What each block shows:

No guarantees: at t=1100 Anna, who has just made a reservation, reads 3 from inv-vlc: a read-your-writes violation. Had the sequence of reads been bcn, vlc, bcn (change the seed and you will see it), she would have read 2, 3, 2: a monotonic reads violation. It is literally the story of Mark and the cheese from 02-05, now with Anna herself as the victim.
Sticky session: by always reading from inv-bcn, where she wrote, Anna sees her reservation from the very first moment. The cost is that the load is not spread and that if inv-bcn goes down, Anna's session breaks.
Client with minimum version: Anna carries minimum = 2 with her. When the load balancer sends her to inv-vlc before t=1300, inv-vlc only has version 1, so the client discards it and tries the other replica (which is why the first three reads end up on inv-bcn even though the order in which replicas are tried is random). At t=1400 the propagation has arrived and inv-vlc answers with version 2. If both replicas were lagging, the client would wait (TimeoutError) rather than lie. Note that apply never goes back a version: that is what provides monotonic writes at the replica level.

In a real system, the "version number" would be the LSN of the PostgreSQL WAL, the Kafka offset, or a vector stamp like the one in 01-05; we will see this in 03-04 when we set up the km0_orders replica for real.

Comparison table: model, guarantee, cost and use at Kilometre Zero

Model	Guarantee (in one sentence)	Typical cost	Where Kilometre Zero uses it
Strict consistency	Read = latest write by a global clock	Unachievable	Never (theoretical reference)
Linearizability	Total order that respects real time; each operation is atomic at one instant	Coordination latency on every operation; unavailable during partitions	Reserving the last `aged-cheese`; locks and leader election (etcd, 03-03); balance in `payments`
Strict serializability	Transactions in a sequential order that respects real time	The most expensive; needs bounded clocks or global coordination	None today; a candidate if `payments` ever needed distributed multi-object transactions
Serializability	Transactions equivalent to some sequential order	Aborts on conflict, latency	Inside each service, PostgreSQL with `SERIALIZABLE` on `km0_orders`
Sequential consistency	Total order that respects each process's order	A leader that orders; replicas may lag	Position history of `van-3` (everyone sees the same route)
Causal consistency	Only causally related operations are ordered	Vector stamps or equivalents; per-operation metadata	Questions and answers on producer pages; order comments
Client-centric	Read-your-writes, monotonic reads/writes, writes-follow-reads for each session	Sticky sessions or client-side versions	Anna's profile and address; basket; "my orders"
Strong eventual consistency (CRDT)	Replicas with the same updates have the same state, with no reconciliation	Restricted data types; no support for global invariants	Sales counters per campaign, page visits, "likes"
Eventual consistency	Replicas converge if writes stop	Almost nil; anomalies of every kind in the meantime	Catalogue cache in Redis; search index; `analytics` aggregates

The important takeaway from the table is that Kilometre Zero does not choose one model, it chooses one per piece of data. The same platform needs linearizability for the last unit and is happy with eventual consistency for the number of visits. Justifying every row of the last column in the face of network failures is exactly the subject of the next lesson.

Common Mistakes and Tips

Saying "consistent" with no qualifier. In a design meeting, "the database is consistent" means nothing. Always ask: linearizable? serializable? causal? eventual with what reconciliation? The answer changes the architecture.
Confusing the C of ACID with the C of CAP. ACID consistency is "transactions respect the schema's invariants" (foreign keys, constraints). The consistency of this lesson's models is about the order of reads and writes across replicas. They have nothing to do with each other, and in 03-02 the C of CAP will specifically be linearizability.
Confusing serializability with linearizability. A SERIALIZABLE distributed database can return you a stale read after your transaction has committed. If you need both, the term you are looking for is strict serializability, and the price is high.
Believing that "eventual" is a deadline. It is not. If a requirement says "eventually consistent, within one second", that second is an operational objective (SLO) that has to be measured (07-01), not a guarantee of the model.
Asking for linearizability everywhere just in case. Every linearizable operation crosses the network at least once with coordination. Applying it to the pink-tomato visit counter would multiply latency for no benefit. Classify your data as in the table in section 11.
Forgetting session guarantees when adding read replicas. The most frequent mistake in practice: a replica is added to scale reads and suddenly users "lose" what they have just saved. Before routing reads to replicas, decide whether you will use sticky sessions or versions.
Tip: when you design a service, write next to each table or entity the consistency model it needs and the specific anomaly that model prevents. If you cannot name the anomaly, the weak model is probably enough.

Exercises

Exercise 1: Classifying histories

The stock of crianza-wine from Roble Alto Winery starts at 5. For each history, state whether it is linearizable, whether it is sequentially consistent and whether it is causally consistent (give your reasoning, and check linearizability with is_linearizable):

History H1

Op	Client	Start	End	Operation
A	Anna	0	10	write 4
B	Mark	20	30	write 3
C	Lucy	40	50	read → 4

History H2 (two processes, no times, only the order within each one)

Anna: write 4; read → 4; read → 3
Mark: write 3; read → 3; read → 4

Exercise 2: Diagnosing the session anomaly

A user reports the following in the Kilometre Zero app: "I added zucchini to the basket, went to the payment tab and the basket was empty; I went back and the zucchini was there; I went to payment again and it was empty again". The basket lives on two replicas with asynchronous replication and a round-robin load balancer. State which session guarantees are violated, which of the two techniques from section 9 you would apply, and what drawback each one would have in the specific case of a basket.

Exercise 3: A CRDT that should not be one

Modify GCounter to obtain a PNCounter (increments and decrements, with two internal G-Counters, positives and negatives). Use it to model the stock of fresh-cheese (initially 1) with inv-bcn and inv-vlc each concurrently deducting one unit, merge and print the value. Explain why the result shows that stock must not be modelled as a CRDT, and which piece of Kilometre Zero data would be a good fit for a PNCounter.

Solutions

Solution 1:

H1: A finishes (10) before B starts (20), and B finishes (30) before C starts (40); real time forces the order A, B, C. In that order C should read 3, but it read 4: it is not linearizable. Without the time constraint, the order B, A, C is valid (each process has a single operation, so program order constrains nothing) and C reads 4: it is sequentially consistent, and therefore also causally consistent (A and B are concurrent in the causal sense, so Lucy may see them in any order). is_linearizable returns None for H1 with initial_value=5.

H2: there are no times, so linearizability cannot be assessed beyond the sequential part. Is there a total order that respects each one's program order? Anna needs to see 4 and then 3, so in the total order her write of 4 precedes Mark's (3), or at least Anna reads in between; Mark needs to see 3 and then 4, so the write of 3 precedes the write of 4. The two requirements contradict each other in a single total order: it is not sequentially consistent. However, the two writes are causally concurrent (neither process read the other's write before writing), so each process may apply them in a different order and the reads are legal: it is causally consistent. This is the classic example of the difference between the two models.

Solution 2:

Monotonic reads is violated (the user sees the basket with the zucchini, then empty, then with the zucchini: it goes back in time) and, on the first visit to payment, so is read-your-writes (they have just written the zucchini and do not read it). Round-robin guarantees precisely that replicas alternate, the worst possible option without session guarantees.

Sticky session: the load balancer always routes each user to the same replica (by cookie or by a hash of the user id). It solves both anomalies with zero changes to the application. Drawback for a basket: if the replica goes down, the user loses their session halfway through a purchase (or has to wait for the other replica to reach the version); besides, a user with a phone and a browser could land on different replicas if stickiness is per connection rather than per user.
Client-side version: the app stores the basket version after every write and sends it with every read; a replica that has not reached it redirects or waits. It tolerates replica crashes and works across several devices. Drawback: both client and server have to be changed, and in the worst case (all replicas lagging) the read waits. For a basket, the second is preferable; a common alternative is to route all basket operations, reads included, to the primary node, giving up read scaling for that small, critical piece of data.

Solution 3:

from gcounter import GCounter


class PNCounter:
    def __init__(self, replicas: list[str]):
        self.positives = GCounter(replicas)
        self.negatives = GCounter(replicas)
    def increment(self, replica: str, n: int = 1) -> None:
        self.positives.increment(replica, n)
    def decrement(self, replica: str, n: int = 1) -> None:
        self.negatives.increment(replica, n)
    def value(self) -> int:
        return self.positives.value() - self.negatives.value()
    def merge(self, other: "PNCounter") -> None:
        self.positives.merge(other.positives)
        self.negatives.merge(other.negatives)

replicas = ["inv-bcn", "inv-vlc"]
bcn, vlc = PNCounter(replicas), PNCounter(replicas)
bcn.increment("inv-bcn", 1)            # 1 fresh cheese arrives and is propagated to both
vlc.merge(bcn)
bcn.decrement("inv-bcn")               # Anna reserves it in Barcelona
vlc.decrement("inv-vlc")               # Mark reserves it in Valencia, concurrently
print(bcn.value(), vlc.value())        # 0 0: each replica believes it has sold the last one
bcn.merge(vlc); vlc.merge(bcn)
print(bcn.value(), vlc.value())        # -1 -1

The CRDT has done exactly what it promises: the two replicas converge to the same state with no coordination. But the state is -1: a cheese that does not exist has been sold. A CRDT guarantees convergence, not invariants that depend on seeing the global state before deciding (such as "do not deduct if there are zero left"). Deciding on the last unit requires somebody to have the final say, that is, linearizability or at least coordination (03-02, 03-03). A PNCounter is a good fit for data where subtracting violates nothing: units reserved and later released in a statistical campaign counter, or the number of items in Anna's wish list (adding and removing with no meaningful lower bound).

Conclusion

A consistency model is the contract that determines which histories of reads and writes a replicated store may produce, and this lesson has walked down the hierarchy of contracts with the vocabulary we will use for the rest of the course. Strict consistency is a physical ideal that is impossible without a global clock; linearizability is its achievable version, where each operation appears atomic at some point between its start and its end, and we have checked by hand and with is_linearizable that the history of Mark seeing Anna's cheese does not satisfy it. Serializability talks about transactions and does not respect real time, and its union with linearizability is the expensive strict serializability. Moving down the hierarchy, sequential consistency only requires each process's order to be respected; causal consistency, only the order of what is related by happens-before, which links it to the vector clocks of 01-05 and makes it the strongest model compatible with availability; and eventual consistency only promises convergence, unless you use a CRDT such as GCounter, which turns merging into a deterministic operation at the price of giving up invariants like "stock never drops below zero". The client-centric guarantees (read-your-writes, monotonic reads, monotonic writes, writes-follow-reads) have turned out to be the ones Anna really notices, and the simulation of inv-bcn and inv-vlc has shown how sticky sessions and client-side versions restore them on top of lagging replication. The final table makes it clear that Kilometre Zero does not choose one model, but one per piece of data.

One question remains that the table dodges: why not give everything linearizability? If inv-bcn and inv-vlc cannot talk to each other for thirty seconds because a router in Barcelona has rebooted, the reservation of the last cheese can wait, or it can be accepted on both sides and sorted out afterwards, but it cannot be both linearizable and available in the two cities at once. That impossibility has a name and a formal statement, is misunderstood more often than it is understood, and has an extension that also talks about latency in the absence of failures. It is the subject of the next lesson: the CAP theorem and PACELC.

Consistency Models

Contents

A consistency model is a contract

The hierarchy of models

Linearizability and the unachievable ideal of strict consistency

Strict consistency

Linearizability

Checking the linearizability of a history by hand (and in Python)

Serializability: similar, but not the same thing

Sequential consistency

Causal consistency: happens-before applied to data

Eventual consistency and strong eventual consistency (CRDTs)

Client-centric models: what Anna expects from her session

Simulation: `inv-bcn` and `inv-vlc` with delayed propagation

Comparison table: model, guarantee, cost and use at Kilometre Zero

Common Mistakes and Tips

Exercises

Exercise 1: Classifying histories

Exercise 2: Diagnosing the session anomaly

Exercise 3: A CRDT that should not be one

Solutions

Conclusion

Distributed Architectures Course

Module 1: Introduction to Distributed Systems

Module 2: Communication in Distributed Systems

Module 3: Consistency and Replication

Module 4: Distributed Storage

Module 5: Distributed Computing

Module 6: Security in Distributed Systems

Module 7: Monitoring and Maintenance

Module 8: Case Studies and Applications

Consistency Models

Contents

A consistency model is a contract

The hierarchy of models

Linearizability and the unachievable ideal of strict consistency

Strict consistency

Linearizability

Checking the linearizability of a history by hand (and in Python)

Serializability: similar, but not the same thing

Sequential consistency

Causal consistency: happens-before applied to data

Eventual consistency and strong eventual consistency (CRDTs)

Client-centric models: what Anna expects from her session

Simulation: inv-bcn and inv-vlc with delayed propagation

Comparison table: model, guarantee, cost and use at Kilometre Zero

Common Mistakes and Tips

Exercises

Exercise 1: Classifying histories

Exercise 2: Diagnosing the session anomaly

Exercise 3: A CRDT that should not be one

Solutions

Conclusion

Distributed Architectures Course

Module 1: Introduction to Distributed Systems

Module 2: Communication in Distributed Systems

Module 3: Consistency and Replication

Module 4: Distributed Storage

Module 5: Distributed Computing

Module 6: Security in Distributed Systems

Module 7: Monitoring and Maintenance

Module 8: Case Studies and Applications

Simulation: `inv-bcn` and `inv-vlc` with delayed propagation