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)statesboth-CSstuckverdict
check-then-set flags3610UNSAFE
set-then-check flags3201SAFE, CAN STALL
strict alternation3004SAFE, CAN STALL
Hyman 19669620UNSAFE
Peterson 19816200SAFE
Dijkstra 1965, n=247700SAFE
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