Atomic File-Lock Protocols for Multiple Windows: Self-Recovering Orphan Locks after Power Loss and Cross-Window Hand-Over State Machines: chapter answers
When several writing windows claim volume numbers at once, the commonest code checks whether a lock exists, creates it if not, and adds a timeout said to repair the lock after a power cut. The commissioning claim was that check-then-create must have a race window, that only atomic exclusive creation guarantees mutual exclusion, and that a self-repairing lease without a monotonic clock and fencing tokens produces two holders. This book writes every step of a protocol as an atomic operation, simulates the file system in memory, enumerates every interleaving and corrects the blueprint in four pl…
DOI pending · monograph page goes live after publication · 5DL-B-254 · 中文版
- Chapter 1 · The Race Window: Exhaustive Interleavings of Check-then-Create and Their Width on the Wall Clock
Program p11 counted every schedule: with two windows using check-then-create, 12 of 16 schedules give a double claim; with four windows, 74880 of 74976. Atomic exclusive creation has no bad schedule at any window count.… - Chapter 2 · Mutual Exclusion from Reads and Writes Alone: Model-Checking Six Entry Protocols and the Roster Bound
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. - Chapter 3 · After the Power Cut: Empty Locks, Missing Status and Write-Temporary-then-Link
Program p31 shows that when a claim is cut short by a power failure, the original method can leave 7 disk states in the lagging model, 3 of them empty locks; flushing reduces empty locks to 1 kind but cannot remove it;… - Chapter 4 · Leases, Clocks and Fencing Tokens
Program p41 showed that steps of a single shared clock create no overlap, while mixing a monotonic clock with the wall clock does: a 5-second step gives 3.000 seconds of overlap, and a 3600-second step gives 58.000 seco… - Chapter 5 · Judging Orphan Locks: How Long a Silence Means Death
Chapter 5 treats the judgement of orphans: an hour of silence on a laptop says little about death, and once automatic stealing is allowed even release gives double claims, 12 of 80 schedules, a share of 0.150. - Chapter 6 · State Machines for Hand-Over between Windows: Transfer, Tokens and a Status That Only Moves Forward
Program p61 showed that hand-over by delete-then-create is overtaken by a third party in 40 of 54 schedules; atomic replacement removes the queue-jumping, yet 0.250 of schedules are still damaged by the departing window… - Chapter 7 · Classical Sources East and West: the Gatekeeper Who "Keeps and Issues the Keys" and Dijkstra in 1965
Chapter 7 examines "he keeps and issues the keys, to open and close the gates of the state" from the Office of the Gates in the Rites of Zhou and Dijkstra's four conditions of 1965. - Chapter 8 · Closing the Loop: a Formal Health Check of This Series' Lock Protocol and a Pre-Registered Test
Chapter 8 gives a formal health check of the lock protocol this series uses: none of its schedules gives a double claim as written, while an automatic cleaner gives double claims in 45 of 48 final states. It presents th…
Illustrative model calculation, not a live quote