"""The crash sweep: kill the coordinator at every step of the schedule and count what the survivors can work out. Nothing here is hand-staged. The schedule is deterministic, so `k` runs from 0 to the length of a clean run and every row is a real execution. python3 demo.py """ from tpc import (Sim, run_crash_at, blocked_timings, total_steps, PREPARED, COMMITTED, ABORTED, INIT) BAR = "=" * 70 ALL_YES = ["yes", "yes", "yes"] ONE_NO = ["yes", "no", "yes"] def section(title): print(f"\n{BAR}\n{title}\n{BAR}") # ---------------------------------------------------------------- 1. the run section("1. A clean run. 3 participants, all vote YES, nobody crashes.") s = Sim(ALL_YES) n = s.run() for i, line in enumerate(s.trace, 1): print(f" {i:2} {line}") print(f"\n {n} steps. Final states: {s.outcomes()} locks held: {s.locks_held()}") print(" Note step 12: the coordinator has every vote, decides, and forces") print(" 'commit' to its log. Steps 13-15 put that decision on the wire.") print(f" Coordinator's forced log: {s.coord.log}") # ------------------------------------------------------------- 2. the sweep def sweep(votes, label): blocked, n = blocked_timings(votes) section(f"2. {label} votes={votes}") print(f" A clean run is {n} steps, so there are {n + 1} distinct crash") print(f" timings: k=0 (died before sending anything) .. k={n} (died after") print(" the last message). Kill the coordinator at each one.\n") print(" k resolution P1 P2 P3 locks") for k in range(n + 1): sim, res = run_crash_at(votes, k) o = sim.outcomes() flag = " <== BLOCKED FOREVER" if res == "BLOCKED" else "" print(f" {k:2} {str(res):10} {o[1]:9} {o[2]:9} {o[3]:9} " f"{sim.locks_held():5}{flag}") pct = 100 * len(blocked) / (n + 1) print(f"\n blocked at k = {blocked}") print(f" BLOCKED {len(blocked)}/{n + 1} crash timings = {pct:.1f}%") return blocked, n b_yes, n_yes = sweep(ALL_YES, "ALL YES -- the transaction SUCCEEDS") b_no, n_no = sweep(ONE_NO, "ONE NO -- the transaction is VETOED") section("3. The headline") print(f" all-YES : {len(b_yes)}/{n_yes + 1} crash timings block = " f"{100 * len(b_yes) / (n_yes + 1):.1f}%") print(f" one-NO : {len(b_no)}/{n_no + 1} crash timings block = " f"{100 * len(b_no) / (n_no + 1):.1f}%") print("\n The transaction that SUCCEEDS is the one that can hang the cluster.") print(" The transaction that gets vetoed cannot, ever.") print("\n Arithmetic for the 25 all-YES timings:") print(" k=0,1,2 not every PREPARE is on the wire, so some participant is") print(" still `init`. It never voted, so commit was impossible") print(" and abort is safe. 3 timings") print(" k=3..12 every participant is `prepared`, none has heard a") print(" decision. 10 timings, STUCK") print(" k=13..24 a decision message reached somebody; the peer query finds") print(" it and the group resolves. 12 timings") print(" 3 + 10 + 12 = 25. 10/25 = 40.0%") # --------------------------------------------------- 4. why waiting is futile section("4. Why no timeout can help: the uncertainty set holds both outcomes") def local_state(sim, pid): """Everything P1 could ever consult without talking to another node.""" p = sim.parts[pid] return dict(state=p.state, my_vote=p.vote, forced_log=list(p.log), locks=p.locks) def find(votes, decision): """Search (don't assume) for a crash step where the coordinator had forced `decision` and P1 is still uncertain.""" for k in range(total_steps(votes) + 1): sim, _ = run_crash_at(votes, k, recovery="none") if sim.coord.log == [decision] and sim.parts[1].state == PREPARED: return k, sim raise AssertionError("no such step") kA, simA = find(ALL_YES, "commit") kB, simB = find(ONE_NO, "abort") a, b = local_state(simA, 1), local_state(simB, 1) print(f" WORLD A (k={kA}): all three vote YES. The coordinator decides COMMIT,") print(" forces the record, and dies before transmitting it.") print(f" WORLD B (k={kB}): P2 votes NO. The coordinator decides ABORT, forces") print(" the record, and dies before transmitting it.\n") print(f" P1's complete local state, world A: {a}") print(f" P1's complete local state, world B: {b}") print(f" IDENTICAL? {a == b}") assert a == b, "the entire argument depends on this" print(f"\n coordinator's forced log, world A: {simA.coord.log} -> correct: COMMIT") print(f" coordinator's forced log, world B: {simB.coord.log} -> correct: ABORT") print("\n Byte-identical local state; opposite correct answers. A timeout") print(" carries no information, so whichever way P1 jumps there is a world") print(" on the identical state where it is wrong.\n") print(f" And the peers, world A at k={kA}:") for pid, p in sorted(simA.parts.items()): print(f" P{pid}: state={p.state:9} log={str(p.log):22} locks={p.locks}") print(" Every peer is in exactly P1's position, so asking all of them") print(" returns P1's own uncertainty three times. The deciding bit is not") print(f" in the cluster at all -- it is on the dead coordinator's disk.\n") print(f" Contrast, world B at k={kB}:") for pid, p in sorted(simB.parts.items()): print(f" P{pid}: state={p.state:9} log={str(p.log):22} locks={p.locks}") print(" P2 is ABORTED and alive. One peer query reaches it and the group") print(" resolves. The NO voter never entered the uncertainty period, which") print(" is exactly why one-NO never blocks.") # ------------------------------------------------- 5. what is held hostage section("5. What the locks are actually protecting") decided, undecided = [], [] for k in b_yes: sim, _ = run_crash_at(ALL_YES, k, recovery="none") (decided if sim.coord.log else undecided).append(k) print(f" k={k:2}: locks still held = {sim.locks_held()} " f"coordinator log = {sim.coord.log}") print(f"\n coordinator HAD forced a decision: k={decided} " f"({len(decided)} of {len(b_yes)})") print(f" coordinator had decided NOTHING: k={undecided} " f"({len(undecided)} of {len(b_yes)})") print(f"\n In {len(undecided)} of the {len(b_yes)} blocked timings nothing was") print(" committed and abort was legal the whole time. The cluster freezes") print(f" all {len(b_yes)} times anyway, because a participant cannot tell those") print(f" {len(undecided)} apart from the {len(decided)}.") # ------------------------------------------------ 6. refusing to block section("6. The counterfactual: refuse to block, and guess instead") def classify(sim): """(split?, stale?). A participant still INIT never joined the transaction, so its effective outcome is ABORTED -- counting `init` as a state of its own reports a split at k=1,2 that is not one.""" finals = {(ABORTED if p.state == INIT else p.state) for p in sim.parts.values()} split = len(finals) > 1 stale = False if sim.coord.log and not split: want = COMMITTED if sim.coord.log[0] == "commit" else ABORTED stale = finals != {want} return split, stale print(" SPLIT = participants disagree with EACH OTHER (atomicity gone).") print(" STALE = they agree, but opposite to the decision the coordinator") print(" already forced to its log and will hand out on restart.\n") print(" trace policy blocked split stale split at k") for votes, label in ((ALL_YES, "all-YES"), (ONE_NO, "one-NO ")): n = total_steps(votes) for recovery, heur in (("terminate", None), ("unilateral", "abort"), ("unilateral", "commit")): splits, stales, blocked = [], [], [] for k in range(n + 1): sim, res = run_crash_at(votes, k, recovery=recovery, heuristic=heur) if res == "BLOCKED": blocked.append(k) continue sp, st = classify(sim) if sp: splits.append(k) if st: stales.append(k) name = recovery + (f"/{heur}" if heur else "") print(f" {label} {name:24} {len(blocked):3}/{n + 1:<3} " f"{len(splits):5} {len(stales):5} {splits}") print("\n The split, step by step, under presumed-abort on the all-YES trace:") for k in range(11, 17): sim, _ = run_crash_at(ALL_YES, k, recovery="unilateral", heuristic="abort") o = sim.outcomes() sp, st = classify(sim) tag = "SPLIT BRAIN" if sp else ("stale (all wrong)" if st else "ok") print(f" k={k:2} log={str(sim.coord.log):11} " f"P1={o[1]:9} P2={o[2]:9} P3={o[3]:9} {tag}") print("\n Two adjacent steps decide whether the database is consistent.") print(" Presumed-abort is not a fix; it is a choice to be WRONG 3/25 of the") print(" time instead of STUCK 10/25 of the time.") # ------------------------------------------------------- 7. the boundary section("7. The boundary: where does the blocking vanish?") print(" (a) Not with cluster size. steps = 8N, blocked = 3N+1:\n") print(" N steps timings blocked fraction window") for N in range(1, 9): blocked, n = blocked_timings(["yes"] * N) assert n == 8 * N and len(blocked) == 3 * N + 1, (N, n, len(blocked)) print(f" {N:2} {n:5} {n + 1:7} {len(blocked):7} " f"{100 * len(blocked) / (n + 1):6.2f}% k={blocked[0]}..{blocked[-1]}") print("\n Closed form asserted against every N above. (3N+1)/(8N+1) falls") print(" to 3/8 = 37.5% and stays there. You cannot size your way out.\n") print(" (b) It is the VOTE, and it is a cliff. N=5, varying the NO count:\n") print(" NO voters timings blocked fraction") for j in range(0, 6): votes = ["no"] * j + ["yes"] * (5 - j) blocked, n = blocked_timings(votes) print(f" {j:9} {n + 1:7} {len(blocked):7} " f"{100 * len(blocked) / (n + 1):6.2f}%") print("\n Zero NO voters blocks 16/41. One NO voter blocks 0. So does two,") print(" three, four, five. One veto is the entire boundary.") section("A caveat about the 40.0%") print(" 40.0% is a fraction of SCHEDULE STEPS, and step granularity is a") print(" modelling choice -- splitting SEND from DELIVER is what makes") print(" 'crashed after deciding, before transmitting' expressible at all.") print(" A different granularity moves the percentage.") print("\n What does NOT depend on it: the all-YES vs one-NO contrast, run on") print(" the identical model, and the exact closed form blocked = 3N+1 out") print(" of 8N+1 timings. Treat 40.0% as this model's reading of a real") print(" window, not as a law of nature.")