The request
Two-process mutual exclusion model checking study
Read the full request
Create an offline, standard-library Python model-checking study of two-process mutual exclusion. No UI or web server. Model sequential consistency with state (pc0,pc1,flag0,flag1,turn), initially (0,0,false,false,0). Each transition advances exactly one process i, j=1-i: pc=0 sets flag[i]=true and pc[i]=1; pc=1 sets turn=j and pc[i]=2; pc=2 advances to pc[i]=3 iff not flag[j] OR turn==i; pc=3 exits by setting flag[i]=false and pc[i]=0. All other components stay unchanged. pc=3 denotes critical section. Exhaustively BFS every reachable state, recording every labeled edge, and check that both pcs are never 3 and that every reachable state enables at least one transition. Compare a buggy variant changing ONLY the pc=2 guard to not flag[j]; all other transitions stay identical. Find and emit a shortest reachable deadlock trace in the buggy variant, and state whether mutual exclusion still holds. Deliver model_check.py, results.json containing canonical states and edges for BOTH variants, and analysis.md explaining assumptions and results. Add reproducible checks that replay every counterexample transition and compare reported counts to independently recomputed graph counts. Explicitly distinguish deadlock-freedom from fairness/starvation-freedom: do not claim that the stated checks prove fairness. Keep proof observations in the final summary, with reader-facing explanations in the document.
The journey
- Read the requestTurned it into a list of things it would have to prove before calling the work done.
- Did the workPlanned the pieces, built them and checked the result as it went.
- Delivered3 files handed over.
The result
- analysis.md4.9 KB
- model_check.py7.1 KB
- results.json10.4 KB