Part 7 · Failure

Consistency Models, Causality, Ordering, and Linearizability

Lesson 15 took away your two comforting illusions: that nodes can tell a crash from a slowdown, and that two machines share a clock. We patched the latter with a fencing token — a monotonically increasing number that lets a resource reject a stale leader's writes. But that token quietly assumed something big: that the system can hand out one agreed sequence of numbers that everybody respects. What does it even mean for a distributed store to "agree" on an order, given replication lag (lesson 08) and unsynchronized clocks (lesson 15)? This lesson builds the vocabulary for that question — a ladder of consistency models from weak to strong — and names the rung at the top: linearizability, the illusion that there is a single copy of the data. It is the most useful and the most expensive guarantee in distributed systems, and lesson 17 will spend an entire chapter learning how to actually build it.

DDIA source

Arc drawn from Martin Kleppmann, Designing Data-Intensive Applications, Chapter 9 (Consistency and Consensus) — the consistency-model hierarchy, linearizability and its cost, the CAP theorem, and causal consistency / ordering. This lesson covers the consistency half; lesson 17 covers consensus. Original synthesis; ML-infra framings are ours. Careful: linearizability (Ch.9) is not serializability (Ch.7, lesson 13) — §3 keeps them apart.

Linear position

Prerequisite: Lesson 08 (replication lag and the read anomalies — read-your-writes, monotonic reads — that a lagging follower causes) and lesson 15 (a write can arrive late, clocks disagree, and a fencing token is a monotonic counter that orders contending writers). We build directly on both.
New capability: Name precisely what reads a system promises to allow; tell linearizability apart from serializability; know why causal consistency is the strongest model you can keep and stay available under a partition; and put a number on what a strong read costs in latency before you ask for one.

The plan

Six moves. (1) Define a consistency model and show why "eventual consistency" is too weak to reason about. (2) Climb the ladder of client-centric guarantees (read-your-writes, monotonic reads, consistent prefix) — cheap, local, and often enough. (3) Define linearizability precisely with an ASCII history, and separate it hard from serializability. (4) Define causality, happens-before, and Lamport timestamps; contrast total vs partial order; explain why causal consistency is the strongest model that survives a partition. (5) Pay the bill: the CAP theorem stated precisely, plus the latency cost of linearizability even with no partition — with a worked cross-region number. (6) Where you actually need linearizability (locks, leader election, uniqueness) — which hands straight to consensus, lesson 17.

1 · What a consistency model is, and why "eventually" is too weak

A consistency model is a contract between the storage system and the application: given a set of concurrent reads and writes from many clients, it spells out which return values a read is allowed to produce. It is not about whether the data is correct, valuable, or well-typed — it is purely about what a reader may legally observe given the writes that have happened. A strong model permits few histories (easy to reason about, expensive to provide); a weak model permits many (cheap, but you must defend against every anomaly it allows).

The weakest useful model is eventual consistency, which you met in replication (lessons 08 and 09): if writes stop, all replicas eventually converge to the same value. That is the entire promise. Notice the two weasel words. "Eventually" has no bound — it could be 5 ms or 5 minutes, and the model does not say. "If writes stop" never happens in a live system. So an eventually-consistent read may return a value that is arbitrarily stale, and you have no way to know how stale.

Why "eventual" defeats reasoning

The problem is not that reads are stale — it is that the contract gives you no handle to reason with. You cannot write "after I do X, a read will see Y," because eventual consistency permits the read to see the old value, then the new value, then (from a different replica) the old value again. A user updates their notification setting to "off," reloads, still sees "on," reloads again, sees "off," reloads a third time on a different server, sees "on." Every one of those is legal under eventual consistency. The anomalies aren't bugs; they're the spec. Stronger models exist precisely to take specific anomalies off the table so you can reason about the ones that remain.

2 · The client-centric ladder: cheap guarantees that are often enough

Between "eventual" and "single copy" sits a ladder of client-centric guarantees — promises about what a single client's session sees, which a system can provide cheaply (usually by routing that client's reads carefully or stamping its requests) without global coordination. They were introduced as the cures for replication-lag anomalies in lesson 08; here is the ladder in order of strength:

Read-your-writes

A client always sees its own prior writes. After you edit your profile and reload, you see the edit — even if other users still see the old value for a moment. Cheap: route a client's reads to a replica known to have its writes, or read from the leader for a short window.

Monotonic reads

A client never sees time go backward: once it has read a value, later reads return that value or newer, never older. Cures the "reload flips on/off/on" anomaly. Cheap: pin a client to one replica (or to replicas that are at least as fresh as the last one it read).

Consistent prefix

If writes happened in a causal order, every reader sees them in an order consistent with that — never an effect before its cause. A reply never appears before the post it answers. This is the session-level shadow of causal consistency (§4).

Causal consistency

The system-wide version: all clients see causally-related operations in cause→effect order, while concurrent operations may be seen in any order. The strongest model still available under a partition (§4). Built on version vectors / Lamport timestamps.

These are not just weaker linearizability — they are a different kind of promise (about one session, or about causal pairs) that costs almost nothing because it never forces global agreement. The senior instinct: reach for the cheapest rung that removes the anomaly your product actually shows the user. A profile page needs read-your-writes. A feed needs consistent prefix so replies don't precede parents. A metrics dashboard tolerates plain eventual. None of these needs the top rung — which is the one we turn to now, and the one that costs real money.

3 · Linearizability: the single-copy illusion

One sentence: linearizability means the system behaves as if there were a single copy of the data, and every read returns the most recent write. (It is also called atomic consistency or strong consistency.) More precisely: every operation takes effect atomically at some single instant between the moment the client issued the call (the invocation) and the moment it got a response. Pick any execution; if you can slide each operation to a single point on one timeline — inside its own call/return window — and the result is a legal single-machine history, the execution was linearizable.

The consequence that matters most is the recency guarantee: the moment one read returns a new value, every read that starts later must also return that new value (or a still-newer one). There is no window where some clients see the new value and others still see the old. The data has, in effect, a single "now."

A LINEARIZABLE history of one register x (initially 0). Time flows right. Each bar is one operation, from its invocation to its response. C1: |--- write(x=1) ---| C2: |-- read -> 1 --| (started after C1 took effect: must see 1) C3: |-- read -> 1 --| (later still: also sees 1) ✓ The write "takes effect" at the dot; once ANY read sees 1, all later reads do. C1: |------●------| <- effective instant somewhere inside the write's window A NON-LINEARIZABLE history (same operations, illegal result): C1: |--- write(x=1) ---| C2: |-- read -> 1 --| C2 already saw the new value... C3: |-- read -> 0 --| ...but C3, which STARTED LATER, sees 0. ✗ Time went backward for the system as a whole. No single instant for the write can explain both reads -> this history is NOT linearizable (recency violated).

This is exactly the guarantee the fencing token of lesson 15 needed under the hood: for a fencing counter to be monotonic globally — so that every later request carries a strictly larger token than every earlier one — the counter itself must be linearizable. Linearizability is what makes "later" a well-defined, system-wide notion.

Linearizability is NOT serializability — keep them apart

These two get conflated constantly; an interviewer will probe exactly here.

Serializability (lesson 13, DDIA Ch.7) is an isolation property of transactions: a set of transactions, each touching many objects, produces a result equivalent to running them one-at-a-time in some serial order. It says nothing about which order, and nothing about real-time recency — a serializable execution may order transactions as if they ran at a time unrelated to the wall clock.
Linearizability (this lesson, Ch.9) is a recency property of single objects: every operation appears to happen at one real-time instant, and reads see the latest write. It says nothing about grouping operations into transactions.
They are orthogonal. You can have either without the other. The combination — transactions in a serial order that also respects real-time, i.e. linearizable and serializable — has its own name: strict serializability (what "Spanner-style external consistency" delivers).

One-line mnemonic: serializability orders transactions; linearizability dates single operations.

4 · Causality, happens-before, and total vs partial order

Linearizability imposes a total order: every operation is comparable to every other, laid out on one line. That is more order than most operations actually need — and forcing it is what makes it expensive. The natural, cheaper notion of order is causality.

Two events are related by happens-before (written A → B) if A could have caused B: A finished before B started on the same node, or B read a value that A wrote, or there is a chain of such links between them. If neither A → B nor B → A, the two events are concurrent — they happened without knowledge of each other, and no causal order between them exists. This is the same "concurrent" you met with write conflicts in lesson 09; version vectors there were detecting exactly the absence of a happens-before relation.

Happens-before defines a partial order: some pairs are ordered (the causally-related ones), and some pairs are simply incomparable (the concurrent ones). Contrast a total order, where every pair is ordered. Causal consistency promises only to respect the partial order — effects never overtake their causes — while leaving concurrent operations free to be applied in any order on each replica. That freedom is the whole point: where there is no causal link, there is nothing to coordinate, so replicas need not talk.

PARTIAL (causal) order — only causal edges; concurrent pairs unordered: post ──→ reply (reply read the post: post → reply) │ ▼ like-of-post (post → like) reply ? like = CONCURRENT (no path between them) TOTAL order (what linearizability forces) — everything on one line: post → like → reply (or post → reply → like — but ONE global sequence, and every node must agree on which)

How does a system track and impose order cheaply? Three mechanisms sit on a ladder of cost and power. Start with the cheapest.

Sequence numbers from a single leader. The cheapest total order is to route every operation through one node and have it hand out a monotonically increasing counter — operation 1, 2, 3, … This is the fencing counter of lesson 15, generalized: one authority, one strictly-increasing number per event. Because every operation gets a distinct number from a single source, you get a total order for free (just sort by the number), and because later operations always get larger numbers, that order is automatically consistent with causality — anything that happened-before was numbered earlier. It is exactly how a single-leader replicated database (lesson 08) orders its writes: the leader's append position is the sequence number. The catch is the obvious one: it needs a leader, and if the leader fails or partitions you must elect a new one and agree where its counter left off — which is consensus (lesson 17). Cheap order, but it inherits the leader's single point of coordination.

Lamport timestamps get a causally-consistent total order without a single leader. Each node keeps a counter; the rule is precise and worth memorizing:

Lamport timestamp = (counter, node-id). Two rules: (1) on any local event: counter += 1 (2) on receiving a msg: counter = max(counter, msg.counter) + 1 <- the key rule compare two timestamps by counter first, break ties by node-id: (c1, id1) < (c2, id2) iff c1 < c2, or (c1 == c2 and id1 < id2) node A (id=1) node B (id=2) a1: (1,1) a2: (2,1) --msg(2)--> b1: max(0,2)+1 = (3,2) <- B "learns" it is causally AFTER a2 b2: (4,2) a1 → a2 → b1 → b2 : all causally ordered, and the counters respect it.

The max-on-receive rule is what makes it work: whenever B hears from A, B fast-forwards its counter past A's, so any event B does afterward is numbered strictly higher than the event it heard about. Hence if A → B then timestamp(A) < timestamp(B), and the node-id tie-break makes every pair comparable, giving a total order consistent with causality. But that totality is bought by flattening concurrency: two genuinely concurrent events still get ordered (by whichever counter/id is smaller), and from two Lamport timestamps alone you cannot tell whether one caused the other or they were concurrent — the information is gone.

Version vectors (lesson 09) keep the concurrency information that Lamport timestamps throw away. Instead of one counter they carry n counters — one per node — so a timestamp records how much it has seen from every node. Comparison then has a third outcome that a single number cannot express:

version vector = [c_A, c_B, c_C, ...] (one counter per node) V1 happened-before V2 iff V1 <= V2 componentwise AND V1 != V2 V1 concurrent with V2 iff neither dominates the other [2,1,0] vs [2,3,0] : first <= second -> the first happened-before the second [2,1,0] vs [1,2,0] : neither dominates -> CONCURRENT (detected, not guessed)

So the same family resolves the same partial order at three different costs. Lamport = one number, total order, but it loses concurrency info (it must pick an order even for unrelated events). Version vectors = n numbers, partial order, and they detect concurrency (the one thing a single number cannot do) — which is exactly why lesson 09 reached for them to flag conflicting writes that need merging. The contrast is the whole point: choose Lamport when you want one agreed line and don't care which unrelated event came first; choose version vectors when you must know two writes were concurrent so you can merge rather than silently drop one.

But notice what even Lamport timestamps do not give you. They totally order events after the fact — but at the moment a node assigns a timestamp, it cannot know whether some other node is about to produce a lower one, so it can never be sure its operation is final at a given position. Enforcing a total order that every node can act on the instant it is decided — "this message is position 3, irrevocably, deliver it now" — is a strictly stronger primitive called total-order broadcast, and it turns out to be equivalent to consensus. That is the bridge into lesson 17: the cheap single-leader sequence numbers above are the simplest way to build it, and consensus is how you keep handing them out when the leader fails.

Why causal is the ceiling for "available under partition"

Causal consistency is provably the strongest consistency model a system can provide while remaining fully available during a network partition. The reason is exactly the partial-order freedom above: to honor causality, a replica only needs the writes that causally precede the one it is applying — and it can buffer a write until those arrive without ever asking another node "what is the latest?" Linearizability cannot do this: its recency guarantee requires knowing about writes that happened with no causal link to you (a concurrent write on another continent), which forces a round trip. That gap — needing to know about acausal, concurrent writes — is precisely what a partition can sever, and is why the next section's CAP boundary falls between causal and linearizable.

5 · The bill: CAP, and the latency you pay even with no partition

The famous CAP theorem is often mis-stated as "pick two of three." Precisely: when a network partition occurs (some nodes cannot reach others), a system that keeps serving must choose between C (linearizable reads/writes) and A (every non-failing node still answers). It cannot have both during the partition, because a node cut off from its peers either refuses to answer (sacrificing A to stay linearizable) or answers from its own possibly-stale copy (sacrificing C to stay available). When there is no partition, CAP says nothing — you can have both. So CAP is really "during a partition, C or A," and the everyday choice is which one your data needs.

Beyond CAP: linearizability costs latency even when nothing is broken

CAP only bites during a partition, which makes it sound rare. The sharper, always-on cost is latency. To guarantee recency, a linearizable operation must coordinate with other replicas (a quorum, or a leader that itself reached a quorum — lesson 09's w + r > n) on every single operation. That coordination is a network round trip you pay constantly, partition or not. A causally/eventually consistent read can be answered from the local replica with no round trip at all. This is the PACELC refinement: if Partition then C-or-A, Else (normal operation) Latency-or-Consistency.

Worked number — a cross-region linearizable read. Suppose three replicas, one each in Virginia, Ireland, and Singapore, with inter-region round-trip time (RTT) of 70 ms between the two nearest. A client in Virginia issues a read.

Linearizable read (quorum, n = 3, r = 2): the local replica must confirm it holds the latest committed value, which means contacting at least one other region and waiting for the reply — one inter-region round trip. Effective read latency ≈ local processing (~1 ms) + 70 ms RTT ≈ 71 ms, on every read. Staleness: 0 by construction.
Causal / eventual read (served from the local Virginia replica): no cross-region trip. Effective read latency ≈ 1 ms. Staleness: bounded only by replication lag — say ~20 ms of typical lag, occasionally more.

So the recency guarantee here costs about 70 ms × (read volume). At 50,000 reads/second that is 50,000 operations each paying an extra 70 ms of coordination latency — a colossal tax to pay on a feed counter or a recommendation cache that no human would notice was 20 ms stale. The discipline writes itself: spend linearizability only where staleness is actually unacceptable. The widget below lets you turn the RTT and consistency knobs and watch effective latency and worst-case staleness trade against each other.

Consistency vs latency — what a read costs per region hop

Set the inter-region RTT and the consistency level. Linearizable pays one round trip on every read (recency, zero staleness). Causal/eventual reads locally (≈1 ms) and accepts staleness up to the replication lag. Watch effective read latency and worst-case staleness move in opposite directions.

inter-region RTT: 70 ms replication lag: 20 ms level:

Effective read latency

—

Worst-case staleness

—

Coordination per read

—

Available under partition?

—

Show the core JS

// linearizable: one inter-region round trip on EVERY read -> recency, 0 staleness,
// but it must reach a peer, so a partition makes it unavailable (CAP: choose C).
// causal/eventual: served locally -> ~1 ms, staleness up to replication lag,
// and it stays available under a partition (CAP: choose A).
const LOCAL = 1;
if (level === "lin") { latency = LOCAL + RTT; staleness = 0;   available = false; }
else                 { latency = LOCAL;       staleness = lag; available = true;  }

6 · Where you actually need linearizability

Having priced it, here is the short list of jobs that genuinely require the single-copy illusion — and the common thread is that all of them enforce a uniqueness or single-winner invariant that causality alone (§4) cannot, because the contending operations are concurrent and causality refuses to order them:

Job	Why linearizability is required
Locks / leases	Only one client may hold the lock at a time. If two clients could both "see" themselves as the holder (stale read), the lock is worthless — this is the fencing-token scenario of lesson 15.
Leader election	The system must agree on exactly one leader. Two nodes each believing they are leader (split brain) corrupts everything downstream.
Uniqueness constraints	A unique username, a unique email, a once-only account number. Two concurrent registrations of the same value must be ordered so exactly one wins — causality can't, because they're concurrent.
Cross-channel consistency	You write a file to object storage, then enqueue a message "process this file." The consumer must not read the queue and find the file missing — the two channels must agree on which write came first.

For an ML platform: model-registry promotion ("which checkpoint is currently serving in prod?") wants linearizability — two trainers must not both believe their checkpoint is the live one. Distributed training leader/rank-0 election wants it. But feature aggregates, recommendation caches, click counters, and analytics rollups do not — they are eventual or causal, served locally, cheap. The senior move is per-operation consistency: one system exposing a strong path for the handful of control-plane invariants and a cheap local path for the high-volume derived reads.

The catch that motivates lesson 17

Every job in that table reduces to the same primitive: get several unreliable nodes to irrevocably agree on one value (who holds the lock, who is leader, which username won). That primitive is consensus, and providing linearizability is essentially equivalent to solving it. So this lesson has defined the goal; lesson 17 builds the machine — total-order broadcast, the Raft/Paxos family, and the coordination services (ZooKeeper, etcd) that productize it.

Failure modes

Unstated model. A system never declares its consistency, so users discover it by accident — stale permissions, a setting that flips back, a username registered twice. The model was eventual; nobody said so.
Assuming linearizable because single-region. A leader plus async followers (lesson 08) is not linearizable: a read from a lagging follower violates recency. "We have one database" does not imply strong reads.
Conflating it with serializability. "It's serializable, so reads are fresh" — no; serializable transactions can be ordered acausally to wall-clock time. You need strict serializability for both.
Linearizability everywhere. Paying the cross-region coordination round trip on every read, including dashboards and caches, then blaming "the network" for p99 latency.
Expecting availability from a strong store under partition. A linearizable system must refuse some requests during a partition (CAP). If it kept answering, it wasn't linearizable.

Decision checklist

For each read path, write down the weakest model that hides the anomaly the user would notice — often read-your-writes or consistent prefix, not linearizable.
Does this operation enforce a uniqueness / single-winner invariant (lock, leader, unique key)? If yes, it needs linearizability → consensus (lesson 17).
Estimate the coordination tax: how many cross-region round trips, at what RTT, times your read/write volume?
During a partition, must this path stay available (choose A, accept staleness) or stay correct (choose C, accept unavailability)?
Are causally-related operations (post→reply, write-file→enqueue-message) tracked so effects never precede causes?
If you claim "strong consistency," is it linearizable, serializable, or both (strict serializable)? Say which.

Checkpoint exercise

Try it

You run a model-serving platform across two regions (RTT 70 ms). (a) The model-promotion control record ("checkpoint v42 is live") is read once per deploy and must never be stale — pick a consistency model and state the per-read latency it costs and why. (b) The feature vectors served on the inference hot path are read 80,000×/s and tolerate ~30 ms of staleness — pick a model, state the latency, and say what you give up. (c) Two training jobs finish at nearly the same instant and both try to promote their checkpoint to "live." Explain why causal consistency cannot pick a winner, and name the primitive (lesson 17) that can. (d) A region gets partitioned from the other; for each of (a) and (b), state whether that path should keep answering or refuse, and cite CAP.

Where this points next

We have defined the prize — linearizability, the single-copy illusion with a recency guarantee — and shown exactly what it buys (uniqueness, locks, leader election) and what it costs (a coordination round trip per operation, and unavailability during a partition). What we have not done is build it. How do a handful of nodes that can crash, slow down, and disagree about the clock (lesson 15) come to irrevocably agree on a single value or a single ordering of events? That is the consensus problem, and lesson 17 shows that linearizable storage, total-order broadcast, locks, and leader election are all the same problem in disguise — then walks the machinery (Raft/Paxos, total-order broadcast) and the coordination services that package it so you rarely have to implement it yourself.

Where is truth?

A consistency model is really a statement of where truth lives and how stale a copy may be. System of record: under linearizability, the abstract single up-to-date copy — concretely the quorum (or the leader that reached one) that holds the latest committed value; under causal/eventual, there is no single "now," only per-replica state that converges. Copies / derived views: the follower and local-region replicas a read may be served from — each a possibly-stale view of the record. Freshness budget: linearizable = zero staleness (recency guarantee) bought at a coordination round trip per op; causal/eventual = staleness bounded only by replication lag (≈20 ms typical in the worked case). Owner: the operation's chosen consistency level decides which copy is authoritative for that read — a per-operation policy, not a global one. Deletion path: a delete is just another write that must propagate under the same model; under eventual consistency a "deleted" value can briefly reappear from a lagging replica until convergence. Reconciliation / repair: causal order via version vectors detects concurrent writes so they can be merged rather than silently dropped; replication catch-up closes the staleness gap. Evidence it is correct: a linearizable history is one where every operation can be placed at a single instant inside its call/return window and the result is a legal single-machine history — the recency check (no read goes backward) is the observable proof.

Takeaway

A consistency model is the contract for what reads may observe. Eventual consistency only promises convergence with no time bound, so you cannot reason with it; the cheap client-centric rungs (read-your-writes, monotonic reads, consistent prefix) remove specific anomalies per-session for near-zero cost. Linearizability is the top: the system behaves as one copy, every operation takes effect at a single real-time instant, and once any read sees a new value all later reads do (the recency guarantee) — which is exactly what makes a fencing token globally monotonic. It is not serializability: serializability orders transactions into some serial order (isolation, lesson 13); linearizability dates single operations in real time (recency); both together is strict serializability. Causality (happens-before, a partial order tracked by Lamport timestamps and version vectors) is the strongest model that stays available under a partition, because it never needs to know about concurrent, acausal writes. The bill is the CAP boundary — during a partition, choose C or A — and, even with no partition, a per-operation coordination latency (≈70 ms cross-region in our worked case) that you should spend only where staleness is truly unacceptable: locks, leader election, uniqueness constraints — i.e., wherever you need consensus (lesson 17).

Interview prompts

Why is eventual consistency hard to build on? (§1 — it promises only that replicas converge "eventually" with no time bound and only if writes stop; a read may return arbitrarily stale values and even appear to go backward, giving you no handle to reason "after X, a read sees Y.")
Define linearizability and its recency guarantee. (§3 — the system behaves as one copy; each operation takes effect atomically at one real-time instant between its invocation and response, so the moment any read returns a new value, all later reads return that value or newer.)
How is linearizability different from serializability? (§3 — serializability is an isolation property of transactions: equivalent to some serial order, no real-time recency. Linearizability is a recency property of single objects. Orthogonal; both together = strict serializability.)
What is causal consistency and why is it the ceiling for staying available under a partition? (§4 — it preserves happens-before (a partial order via Lamport timestamps / version vectors) while letting concurrent ops reorder; a replica needs only the causally-prior writes, never the acausal concurrent ones a partition could hide, so it never has to block on a peer.)
State the CAP theorem precisely, and the cost CAP omits. (§5 — during a network partition a serving system must choose linearizable-C or available-A, not both; when there's no partition you can have both. The omitted always-on cost is latency: a linearizable op pays a coordination round trip every time, ≈71 ms cross-region in the worked example, vs ≈1 ms local for causal/eventual.)
Give two jobs that need linearizability and two that don't. (§6 — need it: locks/leases, leader election, uniqueness constraints, cross-channel ordering — all single-winner invariants causality can't settle. Don't: feature aggregates, recommendation caches, click counters, dashboards — eventual/causal, served locally.)
Contrast single-leader sequence numbers, Lamport timestamps, and version vectors for ordering. (§4 — a single leader handing out a monotonically increasing counter gives a cheap total order consistent with causality but needs a leader (and consensus to fail it over). Lamport timestamps (counter, node-id) with the max-on-receive rule give a leaderless total order consistent with causality but lose concurrency info. Version vectors carry n counters, give the partial order, and uniquely can detect that two events were concurrent.)
State the Lamport max-on-receive rule and why it preserves causality. (§4 — on receiving a message a node sets counter = max(local, msg.counter) + 1, so any event after hearing from A is numbered strictly above A's event; thus A → B implies timestamp(A) < timestamp(B), and the node-id tie-break makes the order total.)