What does Atomic Locks for Many Windows conclude, in numbers, about “Mutual Exclusion from Reads and Writes Alone: Model-Checking Six Entry Protocols and the Roster Bound”?
Answer: Chapter 2 model-checks six entry protocols built from reads and writes, reproduces the shortest counterexample to Hyman's flawed solution of 1966 and shows that the roster is the weak point of read/write algorithms.
Scope of the numbers: Marked boxes separate published evidence, runnable Python calculations (19 programs), classical sources and the author's hypotheses.
Data table
The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 1966
| protocol (2 windows) | states | both-CS | stuck | verdict |
| check-then-set flags | 36 | 1 | 0 | UNSAFE |
| set-then-check flags | 32 | 0 | 1 | SAFE, CAN STALL |
| strict alternation | 30 | 0 | 4 | SAFE, CAN STALL |
| Hyman 1966 | 96 | 2 | 0 | UNSAFE |
| Peterson 1981 | 62 | 0 | 0 | SAFE |
| Dijkstra 1965, n=2 | 477 | 0 | 0 | SAFE |
Show the full program
# Chapter 2. p21: an explicit-state model checker for two windows that
# share only read/write variables, run over six classic entry protocols.
# Every reachable state is enumerated (breadth first). "both in CS"
# counts states breaking mutual exclusion; "stuck" counts states where
# some window is trying yet no window can ever enter again. A window
# may stop for good in its remainder section (Dijkstra 1965 allows it).
from collections import deque
REM, CS, HALT = 0, 50, 99
def put(t, k, v):
t = list(t)
t[k] = v
return tuple(t)
def naive(sh, i, pc, r): # sh = (flag0, flag1); check, then set
j = 1 - i
if pc == 1:
return [(1 if sh[j] else 2, r, sh)]
if pc == 2:
return [(CS, r, put(sh, i, 1))]
return [(REM, r, put(sh, i, 0))] # exit
def setfirst(sh, i, pc, r): # set own flag, then wait on the other
j = 1 - i
if pc == 1:
return [(2, r, put(sh, i, 1))]
if pc == 2:
return [(2 if sh[j] else CS, r, sh)]
return [(REM, r, put(sh, i, 0))]
def alternate(sh, i, pc, r): # sh = (turn,)
if pc == 1:
return [(CS if sh[0] == i else 1, r, sh)]
return [(REM, r, (1 - i,))]
def hyman(sh, i, pc, r): # sh = (b0, b1, k); b = 1 means idle
j = 1 - i
if pc == 1:
return [(2, r, put(sh, i, 0))]
if pc == 2:
return [(CS if sh[2] == i else 3, r, sh)]
if pc == 3:
return [(3 if sh[j] == 0 else 4, r, sh)]
if pc == 4:
return [(2, r, put(sh, 2, i))]
return [(REM, r, put(sh, i, 1))]
def peterson(sh, i, pc, r): # sh = (flag0, flag1, turn)
j = 1 - i
if pc == 1:
return [(2, r, put(sh, i, 1))]
if pc == 2:
return [(3, r, put(sh, 2, j))]
if pc == 3:
return [(3 if sh[j] and sh[2] == j else CS, r, sh)]
return [(REM, r, put(sh, i, 0))]
def dijkstra(sh, i, pc, r, n=2): # sh = b[0..n-1], c[0..n-1], k
b, c, k = sh[:n], sh[n:2 * n], sh[2 * n]
if pc == 1:
return [(2, r, put(sh, i, 0))]
if pc == 2:
return [(7 if k == i else 3, r, sh)]
if pc == 3:
return [(4, r, put(sh, n + i, 1))]
if pc == 4:
return [(5, k, sh)] # read k into r
if pc == 5:
return [(6 if b[r] else 2, r, sh)]
if pc == 6:
return [(2, r, put(sh, 2 * n, i))]
if pc == 7:
return [(8, 0, put(sh, n + i, 0))]
if pc == 8: # scan c[j], j = r
if r == n:
return [(CS, 0, sh)]
if r != i and c[r] == 0:
return [(2, 0, sh)]
return [(8, r + 1, sh)]
if pc == CS + 1:
return [(CS + 2, r, put(sh, n + i, 1))]
return [(REM, r, put(sh, i, 1))]
def moves(alg, state, i):
procs, sh = state
pc, r = procs[i]
if pc == HALT:
return []
if pc == REM:
return [(put(procs, i, (1, r)), sh), (put(procs, i, (HALT, r)), sh)]
if pc == CS:
return [(put(procs, i, (CS + 1, r)), sh)]
return [(put(procs, i, (npc, nr)), nsh)
for npc, nr, nsh in alg(sh, i, pc, r)]
def explore(alg, init):
start = (((REM, 0), (REM, 0)), init)
seen, edges, todo = {start: 0}, {}, deque([start])
while todo:
s = todo.popleft()
out = moves(alg, s, 0) + moves(alg, s, 1)
for t in out:
if t not in seen:
seen[t] = len(seen)
todo.append(t)
edges[s] = out
return seen, edges
def report(name, alg, init):
seen, edges = explore(alg, init)
incs = lambda s: [p for p, _ in s[0] if p == CS]
both = len([s for s in seen if len(incs(s)) == 2])
good = {s for s in seen if incs(s)}
back = {}
for s, out in edges.items():
for t in out:
back.setdefault(t, []).append(s)
todo = deque(good)
while todo:
t = todo.popleft()
for s in back.get(t, []):
if s not in good:
good.add(s)
todo.append(s)
trying = lambda s: [p for p, _ in s[0] if p not in (REM, HALT)]
stuck = len([s for s in seen if trying(s) and s not in good])
verdict = "SAFE" if both == 0 else "UNSAFE"
if both == 0 and stuck:
verdict = "SAFE, CAN STALL"
print("%-22s %6d %8d %6d %s" % (name, len(seen), both, stuck,
verdict))
print("protocol (2 windows) states both-CS stuck verdict")
report("check-then-set flags", naive, (0, 0))
report("set-then-check flags", setfirst, (0, 0))
report("strict alternation", alternate, (0,))
report("Hyman 1966", hyman, (1, 1, 0))
report("Peterson 1981", peterson, (0, 0, 0))
report("Dijkstra 1965, n=2", dijkstra, (1, 1, 1, 1, 0))Single source and citation
Fan, Y. (2026). Atomic File-Lock Protocols for Multiple Windows: Self-Recovering Orphan Locks after Power Loss and Cross-Window Hand-Over State Machines (Version 1.0.0), Chapter 2: Mutual Exclusion from Reads and Writes Alone: Model-Checking Six Entry Protocols and the Roster Bound. 5D Library. DOI pending
DOI pending · monograph page goes live after publication · 5DL-B-254 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026254,
author = {Fan, Yafu},
title = {Atomic File-Lock Protocols for Multiple Windows: Self-Recovering Orphan Locks after Power Loss and Cross-Window Hand-Over State Machines},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
note = {DOI pending}
}Other chapter answers in this book
- Chapter 1 · The Race Window: Exhaustive Interleavings of Check-then-Create and Their Width on the Wall Clock
- Chapter 3 · After the Power Cut: Empty Locks, Missing Status and Write-Temporary-then-Link
- Chapter 4 · Leases, Clocks and Fencing Tokens
- Chapter 5 · Judging Orphan Locks: How Long a Silence Means Death
- Chapter 6 · State Machines for Hand-Over between Windows: Transfer, Tokens and a Status That Only Moves Forward
- Chapter 7 · Classical Sources East and West: the Gatekeeper Who "Keeps and Issues the Keys" and Dijkstra in 1965
- Chapter 8 · Closing the Loop: a Formal Health Check of This Series' Lock Protocol and a Pre-Registered Test