10.8 Worked examples
① Is this history linearizable?
No. C read 1; D's read begins after C's completes, so D must return 1 or newer. Returning 0 moves the linearization point backward in time — the one thing forbidden. (B returning 0 is fine: it overlaps the write.)
② The quorum counterexample, formalized. n=3, w=3, r=2. A's read set {r1,r2} ∩ writer's set = nonempty ✔. B's read set {r2,r3} ∩ writer's set = nonempty ✔. Both satisfy the intersection property, yet B (later) reads older than A. The intersection guarantee only says some replica you read has seen the latest completed write — it says nothing about which value you return when replicas disagree, nor about ordering between two reads.
③ Lamport vs linearizable. Node P and node Q never communicate. P performs op₁ at wall-clock 10:00:00, gets Lamport ts (1, P). Q performs op₂ at 10:00:05 — genuinely later — gets (1, Q). Comparing: (1,P) < (1,Q) by node-ID tiebreak, so the order happens to be right. Now swap the node names: the order is wrong, and nothing detects it. Lamport ordering is only meaningful along communication paths.
④ Cost of a quorum read. 3 nodes, intra-AZ RTT 0.5 ms, inter-AZ 1.5 ms. A linearizable read = leader must confirm leadership with a quorum ⇒ ≥ 1 inter-AZ RTT ≈ 1.5 ms, versus ~0.05 ms for a local stale read — 30×. Across regions (RTT 70 ms), the same read is 1,400× slower. This is Attiya–Welch made concrete: response time proportional to network delay uncertainty.
⑤ Fetch-and-add's consensus number. 3 proposers, counter starts at 0. P reads 0, Q reads 1, R reads 2. Q and R know they lost but not who won. If P crashes before announcing, Q and R can neither decide P's value (they don't know it) nor decide their own (P might return). Termination fails ⇒ consensus number < 3. With 2 proposers, exchanging values first makes the loser able to infer the winner's value — consensus number exactly 2.
⑥ Why quorums must overlap across the two votes. Leader L₁ (epoch 5) is partitioned. L₂ elected in epoch 6 with quorum {A,B,C}. L₁ tries to append with quorum {C,D,E}. The intersection is {C}, and C has seen epoch 6 ⇒ C refuses ⇒ L₁'s append fails. If the quorums could be disjoint ({A,B,C} and {D,E,F} on 6 nodes), both leaders could append conflicting entries — split brain. This single overlap requirement is what makes epochs safe.
⑦ Election timeout budgeting. Worst observed GC pause 800 ms; network p99.9 RTT 20 ms. An election timeout of 500 ms → every long GC on the leader triggers an election → §3.6's election storm. Set it above the worst pause (e.g. 1,500 ms), accept slower failover, or fix the pauses (Ch 9 §4.3). The timeout is a statement about your worst-case pause, not about your network.