Two Threads, One Door
Break a naive lock, explore Peterson's algorithm, and inspect the Lean proof behind the page.
A lock makes a promise: at most one thread gets into the critical section. The difficulty is that two threads can both make a perfectly reasonable decision from an observation that is about to become stale.
This essay is an executable experiment. You choose the schedule. Lean computes the transitions and checks the proofs. Each step below executes a Lean function compiled to WebAssembly, then displays the corresponding diagram. The same transition definition drives the mathematical model and the browser program.
Break the obvious lock
Suppose each thread checks whether a shared Boolean is false, then sets it to true and enters. Those are separate operations. Try the schedule A, B, A, B: both threads read the unlocked state before either records that it has entered. The highlighted line is the thread's next operation. The final line means it is inside the critical section and its next step will leave.
Thread A
- 0
check whether the lock is free - 1
set locked = true and enter - 2
critical section; then unlock
Thread B
- 0
check whether the lock is free - 1
set locked = true and enter - 2
critical section; then unlock
- locked
false
Same final state: these two operations commute at this state.
Step A → Step B
A is ready to check; B is ready to check.
At most one thread insideA is convinced the lock is free; B is ready to check.
At most one thread insideA is convinced the lock is free; B is convinced the lock is free.
At most one thread insideStep B → Step A
A is ready to check; B is ready to check.
At most one thread insideA is ready to check; B is convinced the lock is free.
At most one thread insideA is convinced the lock is free; B is convinced the lock is free.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
check whether the lock is free - 1
set locked = true and enter - 2
critical section; then unlock
Thread B
- 0
check whether the lock is free - 1
set locked = true and enter - 2
critical section; then unlock
- locked
true
Same final state: these two operations commute at this state.
Step A → Step B
A is ready to check; B is ready to check.
At most one thread insideA is ready to check; B is ready to check.
At most one thread insideA is ready to check; B is ready to check.
At most one thread insideStep B → Step A
A is ready to check; B is ready to check.
At most one thread insideA is ready to check; B is ready to check.
At most one thread insideA is ready to check; B is ready to check.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
check whether the lock is free - 1
set locked = true and enter - 2
critical section; then unlock
Thread B
- 0
check whether the lock is free - 1
set locked = true and enter - 2
critical section; then unlock
- locked
false
Different final states: the order of these two operations matters here.
Step A → Step B
A is ready to check; B is convinced the lock is free.
At most one thread insideA is convinced the lock is free; B is convinced the lock is free.
At most one thread insideA is convinced the lock is free; B is inside the critical section.
At most one thread insideStep B → Step A
A is ready to check; B is convinced the lock is free.
At most one thread insideA is ready to check; B is inside the critical section.
At most one thread insideA is ready to check; B is inside the critical section.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
check whether the lock is free - 1
set locked = true and enter - 2
critical section; then unlock
Thread B
- 0
check whether the lock is free - 1
set locked = true and enter - 2
critical section; then unlock
- locked
true
Same final state: these two operations commute at this state.
Step A → Step B
A is ready to check; B is convinced the lock is free.
At most one thread insideA is ready to check; B is convinced the lock is free.
At most one thread insideA is ready to check; B is inside the critical section.
At most one thread insideStep B → Step A
A is ready to check; B is convinced the lock is free.
At most one thread insideA is ready to check; B is inside the critical section.
At most one thread insideA is ready to check; B is inside the critical section.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
check whether the lock is free - 1
set locked = true and enter - 2
critical section; then unlock
Thread B
- 0
check whether the lock is free - 1
set locked = true and enter - 2
critical section; then unlock
- locked
false
Same final state: these two operations commute at this state.
Step A → Step B
A is ready to check; B is inside the critical section.
At most one thread insideA is convinced the lock is free; B is inside the critical section.
At most one thread insideA is convinced the lock is free; B is ready to check.
At most one thread insideStep B → Step A
A is ready to check; B is inside the critical section.
At most one thread insideA is ready to check; B is ready to check.
At most one thread insideA is convinced the lock is free; B is ready to check.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
check whether the lock is free - 1
set locked = true and enter - 2
critical section; then unlock
Thread B
- 0
check whether the lock is free - 1
set locked = true and enter - 2
critical section; then unlock
- locked
true
Different final states: the order of these two operations matters here.
Step A → Step B
A is ready to check; B is inside the critical section.
At most one thread insideA is ready to check; B is inside the critical section.
At most one thread insideA is ready to check; B is ready to check.
At most one thread insideStep B → Step A
A is ready to check; B is inside the critical section.
At most one thread insideA is ready to check; B is ready to check.
At most one thread insideA is convinced the lock is free; B is ready to check.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
check whether the lock is free - 1
set locked = true and enter - 2
critical section; then unlock
Thread B
- 0
check whether the lock is free - 1
set locked = true and enter - 2
critical section; then unlock
- locked
false
Different final states: the order of these two operations matters here.
Step A → Step B
A is convinced the lock is free; B is ready to check.
At most one thread insideA is inside the critical section; B is ready to check.
At most one thread insideA is inside the critical section; B is ready to check.
At most one thread insideStep B → Step A
A is convinced the lock is free; B is ready to check.
At most one thread insideA is convinced the lock is free; B is convinced the lock is free.
At most one thread insideA is inside the critical section; B is convinced the lock is free.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
check whether the lock is free - 1
set locked = true and enter - 2
critical section; then unlock
Thread B
- 0
check whether the lock is free - 1
set locked = true and enter - 2
critical section; then unlock
- locked
true
Same final state: these two operations commute at this state.
Step A → Step B
A is convinced the lock is free; B is ready to check.
At most one thread insideA is inside the critical section; B is ready to check.
At most one thread insideA is inside the critical section; B is ready to check.
At most one thread insideStep B → Step A
A is convinced the lock is free; B is ready to check.
At most one thread insideA is convinced the lock is free; B is ready to check.
At most one thread insideA is inside the critical section; B is ready to check.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
check whether the lock is free - 1
set locked = true and enter - 2
critical section; then unlock
Thread B
- 0
check whether the lock is free - 1
set locked = true and enter - 2
critical section; then unlock
- locked
false
Same final state: these two operations commute at this state.
Step A → Step B
A is convinced the lock is free; B is convinced the lock is free.
At most one thread insideA is inside the critical section; B is convinced the lock is free.
At most one thread insideA is inside the critical section; B is inside the critical section.
Race: both threads are insideStep B → Step A
A is convinced the lock is free; B is convinced the lock is free.
At most one thread insideA is convinced the lock is free; B is inside the critical section.
At most one thread insideA is inside the critical section; B is inside the critical section.
Race: both threads are insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
check whether the lock is free - 1
set locked = true and enter - 2
critical section; then unlock
Thread B
- 0
check whether the lock is free - 1
set locked = true and enter - 2
critical section; then unlock
- locked
true
Same final state: these two operations commute at this state.
Step A → Step B
A is convinced the lock is free; B is convinced the lock is free.
At most one thread insideA is inside the critical section; B is convinced the lock is free.
At most one thread insideA is inside the critical section; B is inside the critical section.
Race: both threads are insideStep B → Step A
A is convinced the lock is free; B is convinced the lock is free.
At most one thread insideA is convinced the lock is free; B is inside the critical section.
At most one thread insideA is inside the critical section; B is inside the critical section.
Race: both threads are insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
check whether the lock is free - 1
set locked = true and enter - 2
critical section; then unlock
Thread B
- 0
check whether the lock is free - 1
set locked = true and enter - 2
critical section; then unlock
- locked
false
Different final states: the order of these two operations matters here.
Step A → Step B
A is convinced the lock is free; B is inside the critical section.
At most one thread insideA is inside the critical section; B is inside the critical section.
Race: both threads are insideA is inside the critical section; B is ready to check.
At most one thread insideStep B → Step A
A is convinced the lock is free; B is inside the critical section.
At most one thread insideA is convinced the lock is free; B is ready to check.
At most one thread insideA is inside the critical section; B is ready to check.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
check whether the lock is free - 1
set locked = true and enter - 2
critical section; then unlock
Thread B
- 0
check whether the lock is free - 1
set locked = true and enter - 2
critical section; then unlock
- locked
true
Different final states: the order of these two operations matters here.
Step A → Step B
A is convinced the lock is free; B is inside the critical section.
At most one thread insideA is inside the critical section; B is inside the critical section.
Race: both threads are insideA is inside the critical section; B is ready to check.
At most one thread insideStep B → Step A
A is convinced the lock is free; B is inside the critical section.
At most one thread insideA is convinced the lock is free; B is ready to check.
At most one thread insideA is inside the critical section; B is ready to check.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
check whether the lock is free - 1
set locked = true and enter - 2
critical section; then unlock
Thread B
- 0
check whether the lock is free - 1
set locked = true and enter - 2
critical section; then unlock
- locked
false
Same final state: these two operations commute at this state.
Step A → Step B
A is inside the critical section; B is ready to check.
At most one thread insideA is ready to check; B is ready to check.
At most one thread insideA is ready to check; B is convinced the lock is free.
At most one thread insideStep B → Step A
A is inside the critical section; B is ready to check.
At most one thread insideA is inside the critical section; B is convinced the lock is free.
At most one thread insideA is ready to check; B is convinced the lock is free.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
check whether the lock is free - 1
set locked = true and enter - 2
critical section; then unlock
Thread B
- 0
check whether the lock is free - 1
set locked = true and enter - 2
critical section; then unlock
- locked
true
Different final states: the order of these two operations matters here.
Step A → Step B
A is inside the critical section; B is ready to check.
At most one thread insideA is ready to check; B is ready to check.
At most one thread insideA is ready to check; B is convinced the lock is free.
At most one thread insideStep B → Step A
A is inside the critical section; B is ready to check.
At most one thread insideA is inside the critical section; B is ready to check.
At most one thread insideA is ready to check; B is ready to check.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
check whether the lock is free - 1
set locked = true and enter - 2
critical section; then unlock
Thread B
- 0
check whether the lock is free - 1
set locked = true and enter - 2
critical section; then unlock
- locked
false
Different final states: the order of these two operations matters here.
Step A → Step B
A is inside the critical section; B is convinced the lock is free.
At most one thread insideA is ready to check; B is convinced the lock is free.
At most one thread insideA is ready to check; B is inside the critical section.
At most one thread insideStep B → Step A
A is inside the critical section; B is convinced the lock is free.
At most one thread insideA is inside the critical section; B is inside the critical section.
Race: both threads are insideA is ready to check; B is inside the critical section.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
check whether the lock is free - 1
set locked = true and enter - 2
critical section; then unlock
Thread B
- 0
check whether the lock is free - 1
set locked = true and enter - 2
critical section; then unlock
- locked
true
Different final states: the order of these two operations matters here.
Step A → Step B
A is inside the critical section; B is convinced the lock is free.
At most one thread insideA is ready to check; B is convinced the lock is free.
At most one thread insideA is ready to check; B is inside the critical section.
At most one thread insideStep B → Step A
A is inside the critical section; B is convinced the lock is free.
At most one thread insideA is inside the critical section; B is inside the critical section.
Race: both threads are insideA is ready to check; B is inside the critical section.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
check whether the lock is free - 1
set locked = true and enter - 2
critical section; then unlock
Thread B
- 0
check whether the lock is free - 1
set locked = true and enter - 2
critical section; then unlock
- locked
false
Same final state: these two operations commute at this state.
Step A → Step B
A is inside the critical section; B is inside the critical section.
Race: both threads are insideA is ready to check; B is inside the critical section.
At most one thread insideA is ready to check; B is ready to check.
At most one thread insideStep B → Step A
A is inside the critical section; B is inside the critical section.
Race: both threads are insideA is inside the critical section; B is ready to check.
At most one thread insideA is ready to check; B is ready to check.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
check whether the lock is free - 1
set locked = true and enter - 2
critical section; then unlock
Thread B
- 0
check whether the lock is free - 1
set locked = true and enter - 2
critical section; then unlock
- locked
true
Same final state: these two operations commute at this state.
Step A → Step B
A is inside the critical section; B is inside the critical section.
Race: both threads are insideA is ready to check; B is inside the critical section.
At most one thread insideA is ready to check; B is ready to check.
At most one thread insideStep B → Step A
A is inside the critical section; B is inside the critical section.
Race: both threads are insideA is inside the critical section; B is ready to check.
At most one thread insideA is ready to check; B is ready to check.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Step 0. A is ready to check; B is ready to check.
Static diagram. Compiled Lean becomes available when browser support is enabled.
No compiled transitions have executed.
The failure is a concrete Lean value. Changing the transition function changes this result, the explorer, and the theorem obligation together.
(Naive.run Naive.race){ a := 2, b := 2, locked := true }GwernPort.Examples.Mutex.Naive.counterexample(Naive.run Naive.race).a = 2 ∧ (Naive.run Naive.race).b = 2Axioms: propext, Classical.choice, Quot.sound
Here a = 2 and b = 2 mean that both program counters point into their
critical sections. The displayed theorem statement and axiom inventory are
read from Lean's environment at elaboration time.
Add a little courtesy
Peterson's algorithm uses a flag for each thread and one shared turn variable. A thread raises its flag, gives the other thread priority, then waits until the other flag is down or the turn favors itself. If both arrive together, the last write to the turn variable gives one of them a reason to wait.
Try to reproduce the race. Reading the other flag and reading the turn are separate steps: either thread may run between them. A waiting thread can spin through those reads until it may enter. Undo and reset let you explore another interleaving without losing your place in the essay.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
false- flag[B]
false- turn
A
Same final state: these two operations commute at this state.
Step A → Step B
A is idle; B is idle. Turn favors A.
At most one thread insideA is holding its flag up; B is idle. Turn favors A.
At most one thread insideA is holding its flag up; B is holding its flag up. Turn favors A.
At most one thread insideStep B → Step A
A is idle; B is idle. Turn favors A.
At most one thread insideA is idle; B is holding its flag up. Turn favors A.
At most one thread insideA is holding its flag up; B is holding its flag up. Turn favors A.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
false- flag[B]
false- turn
B
Same final state: these two operations commute at this state.
Step A → Step B
A is idle; B is idle. Turn favors B.
At most one thread insideA is holding its flag up; B is idle. Turn favors B.
At most one thread insideA is holding its flag up; B is holding its flag up. Turn favors B.
At most one thread insideStep B → Step A
A is idle; B is idle. Turn favors B.
At most one thread insideA is idle; B is holding its flag up. Turn favors B.
At most one thread insideA is holding its flag up; B is holding its flag up. Turn favors B.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
false- flag[B]
true- turn
A
Same final state: these two operations commute at this state.
Step A → Step B
A is idle; B is holding its flag up. Turn favors A.
At most one thread insideA is holding its flag up; B is holding its flag up. Turn favors A.
At most one thread insideA is holding its flag up; B is checking the other flag. Turn favors A.
At most one thread insideStep B → Step A
A is idle; B is holding its flag up. Turn favors A.
At most one thread insideA is idle; B is checking the other flag. Turn favors A.
At most one thread insideA is holding its flag up; B is checking the other flag. Turn favors A.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
false- flag[B]
true- turn
B
Same final state: these two operations commute at this state.
Step A → Step B
A is idle; B is holding its flag up. Turn favors B.
At most one thread insideA is holding its flag up; B is holding its flag up. Turn favors B.
At most one thread insideA is holding its flag up; B is checking the other flag. Turn favors A.
At most one thread insideStep B → Step A
A is idle; B is holding its flag up. Turn favors B.
At most one thread insideA is idle; B is checking the other flag. Turn favors A.
At most one thread insideA is holding its flag up; B is checking the other flag. Turn favors A.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
false- flag[B]
true- turn
A
Different final states: the order of these two operations matters here.
Step A → Step B
A is idle; B is checking the other flag. Turn favors A.
At most one thread insideA is holding its flag up; B is checking the other flag. Turn favors A.
At most one thread insideA is holding its flag up; B is checking the turn. Turn favors A.
At most one thread insideStep B → Step A
A is idle; B is checking the other flag. Turn favors A.
At most one thread insideA is idle; B is inside the critical section. Turn favors A.
At most one thread insideA is holding its flag up; B is inside the critical section. Turn favors A.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
false- flag[B]
true- turn
B
Different final states: the order of these two operations matters here.
Step A → Step B
A is idle; B is checking the other flag. Turn favors B.
At most one thread insideA is holding its flag up; B is checking the other flag. Turn favors B.
At most one thread insideA is holding its flag up; B is checking the turn. Turn favors B.
At most one thread insideStep B → Step A
A is idle; B is checking the other flag. Turn favors B.
At most one thread insideA is idle; B is inside the critical section. Turn favors B.
At most one thread insideA is holding its flag up; B is inside the critical section. Turn favors B.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
false- flag[B]
true- turn
A
Same final state: these two operations commute at this state.
Step A → Step B
A is idle; B is checking the turn. Turn favors A.
At most one thread insideA is holding its flag up; B is checking the turn. Turn favors A.
At most one thread insideA is holding its flag up; B is checking the other flag. Turn favors A.
At most one thread insideStep B → Step A
A is idle; B is checking the turn. Turn favors A.
At most one thread insideA is idle; B is checking the other flag. Turn favors A.
At most one thread insideA is holding its flag up; B is checking the other flag. Turn favors A.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
false- flag[B]
true- turn
B
Same final state: these two operations commute at this state.
Step A → Step B
A is idle; B is checking the turn. Turn favors B.
At most one thread insideA is holding its flag up; B is checking the turn. Turn favors B.
At most one thread insideA is holding its flag up; B is inside the critical section. Turn favors B.
At most one thread insideStep B → Step A
A is idle; B is checking the turn. Turn favors B.
At most one thread insideA is idle; B is inside the critical section. Turn favors B.
At most one thread insideA is holding its flag up; B is inside the critical section. Turn favors B.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
false- flag[B]
true- turn
A
Same final state: these two operations commute at this state.
Step A → Step B
A is idle; B is inside the critical section. Turn favors A.
At most one thread insideA is holding its flag up; B is inside the critical section. Turn favors A.
At most one thread insideA is holding its flag up; B is idle. Turn favors A.
At most one thread insideStep B → Step A
A is idle; B is inside the critical section. Turn favors A.
At most one thread insideA is idle; B is idle. Turn favors A.
At most one thread insideA is holding its flag up; B is idle. Turn favors A.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
false- flag[B]
true- turn
B
Same final state: these two operations commute at this state.
Step A → Step B
A is idle; B is inside the critical section. Turn favors B.
At most one thread insideA is holding its flag up; B is inside the critical section. Turn favors B.
At most one thread insideA is holding its flag up; B is idle. Turn favors B.
At most one thread insideStep B → Step A
A is idle; B is inside the critical section. Turn favors B.
At most one thread insideA is idle; B is idle. Turn favors B.
At most one thread insideA is holding its flag up; B is idle. Turn favors B.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
true- flag[B]
false- turn
A
Same final state: these two operations commute at this state.
Step A → Step B
A is holding its flag up; B is idle. Turn favors A.
At most one thread insideA is checking the other flag; B is idle. Turn favors B.
At most one thread insideA is checking the other flag; B is holding its flag up. Turn favors B.
At most one thread insideStep B → Step A
A is holding its flag up; B is idle. Turn favors A.
At most one thread insideA is holding its flag up; B is holding its flag up. Turn favors A.
At most one thread insideA is checking the other flag; B is holding its flag up. Turn favors B.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
true- flag[B]
false- turn
B
Same final state: these two operations commute at this state.
Step A → Step B
A is holding its flag up; B is idle. Turn favors B.
At most one thread insideA is checking the other flag; B is idle. Turn favors B.
At most one thread insideA is checking the other flag; B is holding its flag up. Turn favors B.
At most one thread insideStep B → Step A
A is holding its flag up; B is idle. Turn favors B.
At most one thread insideA is holding its flag up; B is holding its flag up. Turn favors B.
At most one thread insideA is checking the other flag; B is holding its flag up. Turn favors B.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
true- flag[B]
true- turn
A
Different final states: the order of these two operations matters here.
Step A → Step B
A is holding its flag up; B is holding its flag up. Turn favors A.
At most one thread insideA is checking the other flag; B is holding its flag up. Turn favors B.
At most one thread insideA is checking the other flag; B is checking the other flag. Turn favors A.
At most one thread insideStep B → Step A
A is holding its flag up; B is holding its flag up. Turn favors A.
At most one thread insideA is holding its flag up; B is checking the other flag. Turn favors A.
At most one thread insideA is checking the other flag; B is checking the other flag. Turn favors B.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
true- flag[B]
true- turn
B
Different final states: the order of these two operations matters here.
Step A → Step B
A is holding its flag up; B is holding its flag up. Turn favors B.
At most one thread insideA is checking the other flag; B is holding its flag up. Turn favors B.
At most one thread insideA is checking the other flag; B is checking the other flag. Turn favors A.
At most one thread insideStep B → Step A
A is holding its flag up; B is holding its flag up. Turn favors B.
At most one thread insideA is holding its flag up; B is checking the other flag. Turn favors A.
At most one thread insideA is checking the other flag; B is checking the other flag. Turn favors B.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
true- flag[B]
true- turn
A
Same final state: these two operations commute at this state.
Step A → Step B
A is holding its flag up; B is checking the other flag. Turn favors A.
At most one thread insideA is checking the other flag; B is checking the other flag. Turn favors B.
At most one thread insideA is checking the other flag; B is checking the turn. Turn favors B.
At most one thread insideStep B → Step A
A is holding its flag up; B is checking the other flag. Turn favors A.
At most one thread insideA is holding its flag up; B is checking the turn. Turn favors A.
At most one thread insideA is checking the other flag; B is checking the turn. Turn favors B.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
true- flag[B]
true- turn
B
Same final state: these two operations commute at this state.
Step A → Step B
A is holding its flag up; B is checking the other flag. Turn favors B.
At most one thread insideA is checking the other flag; B is checking the other flag. Turn favors B.
At most one thread insideA is checking the other flag; B is checking the turn. Turn favors B.
At most one thread insideStep B → Step A
A is holding its flag up; B is checking the other flag. Turn favors B.
At most one thread insideA is holding its flag up; B is checking the turn. Turn favors B.
At most one thread insideA is checking the other flag; B is checking the turn. Turn favors B.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
true- flag[B]
true- turn
A
Different final states: the order of these two operations matters here.
Step A → Step B
A is holding its flag up; B is checking the turn. Turn favors A.
At most one thread insideA is checking the other flag; B is checking the turn. Turn favors B.
At most one thread insideA is checking the other flag; B is inside the critical section. Turn favors B.
At most one thread insideStep B → Step A
A is holding its flag up; B is checking the turn. Turn favors A.
At most one thread insideA is holding its flag up; B is checking the other flag. Turn favors A.
At most one thread insideA is checking the other flag; B is checking the other flag. Turn favors B.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
true- flag[B]
true- turn
B
Same final state: these two operations commute at this state.
Step A → Step B
A is holding its flag up; B is checking the turn. Turn favors B.
At most one thread insideA is checking the other flag; B is checking the turn. Turn favors B.
At most one thread insideA is checking the other flag; B is inside the critical section. Turn favors B.
At most one thread insideStep B → Step A
A is holding its flag up; B is checking the turn. Turn favors B.
At most one thread insideA is holding its flag up; B is inside the critical section. Turn favors B.
At most one thread insideA is checking the other flag; B is inside the critical section. Turn favors B.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
true- flag[B]
true- turn
A
Same final state: these two operations commute at this state.
Step A → Step B
A is holding its flag up; B is inside the critical section. Turn favors A.
At most one thread insideA is checking the other flag; B is inside the critical section. Turn favors B.
At most one thread insideA is checking the other flag; B is idle. Turn favors B.
At most one thread insideStep B → Step A
A is holding its flag up; B is inside the critical section. Turn favors A.
At most one thread insideA is holding its flag up; B is idle. Turn favors A.
At most one thread insideA is checking the other flag; B is idle. Turn favors B.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
true- flag[B]
true- turn
B
Same final state: these two operations commute at this state.
Step A → Step B
A is holding its flag up; B is inside the critical section. Turn favors B.
At most one thread insideA is checking the other flag; B is inside the critical section. Turn favors B.
At most one thread insideA is checking the other flag; B is idle. Turn favors B.
At most one thread insideStep B → Step A
A is holding its flag up; B is inside the critical section. Turn favors B.
At most one thread insideA is holding its flag up; B is idle. Turn favors B.
At most one thread insideA is checking the other flag; B is idle. Turn favors B.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
true- flag[B]
false- turn
A
Different final states: the order of these two operations matters here.
Step A → Step B
A is checking the other flag; B is idle. Turn favors A.
At most one thread insideA is inside the critical section; B is idle. Turn favors A.
At most one thread insideA is inside the critical section; B is holding its flag up. Turn favors A.
At most one thread insideStep B → Step A
A is checking the other flag; B is idle. Turn favors A.
At most one thread insideA is checking the other flag; B is holding its flag up. Turn favors A.
At most one thread insideA is checking the turn; B is holding its flag up. Turn favors A.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
true- flag[B]
false- turn
B
Different final states: the order of these two operations matters here.
Step A → Step B
A is checking the other flag; B is idle. Turn favors B.
At most one thread insideA is inside the critical section; B is idle. Turn favors B.
At most one thread insideA is inside the critical section; B is holding its flag up. Turn favors B.
At most one thread insideStep B → Step A
A is checking the other flag; B is idle. Turn favors B.
At most one thread insideA is checking the other flag; B is holding its flag up. Turn favors B.
At most one thread insideA is checking the turn; B is holding its flag up. Turn favors B.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
true- flag[B]
true- turn
A
Same final state: these two operations commute at this state.
Step A → Step B
A is checking the other flag; B is holding its flag up. Turn favors A.
At most one thread insideA is checking the turn; B is holding its flag up. Turn favors A.
At most one thread insideA is checking the turn; B is checking the other flag. Turn favors A.
At most one thread insideStep B → Step A
A is checking the other flag; B is holding its flag up. Turn favors A.
At most one thread insideA is checking the other flag; B is checking the other flag. Turn favors A.
At most one thread insideA is checking the turn; B is checking the other flag. Turn favors A.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
true- flag[B]
true- turn
B
Same final state: these two operations commute at this state.
Step A → Step B
A is checking the other flag; B is holding its flag up. Turn favors B.
At most one thread insideA is checking the turn; B is holding its flag up. Turn favors B.
At most one thread insideA is checking the turn; B is checking the other flag. Turn favors A.
At most one thread insideStep B → Step A
A is checking the other flag; B is holding its flag up. Turn favors B.
At most one thread insideA is checking the other flag; B is checking the other flag. Turn favors A.
At most one thread insideA is checking the turn; B is checking the other flag. Turn favors A.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
true- flag[B]
true- turn
A
Same final state: these two operations commute at this state.
Step A → Step B
A is checking the other flag; B is checking the other flag. Turn favors A.
At most one thread insideA is checking the turn; B is checking the other flag. Turn favors A.
At most one thread insideA is checking the turn; B is checking the turn. Turn favors A.
At most one thread insideStep B → Step A
A is checking the other flag; B is checking the other flag. Turn favors A.
At most one thread insideA is checking the other flag; B is checking the turn. Turn favors A.
At most one thread insideA is checking the turn; B is checking the turn. Turn favors A.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
true- flag[B]
true- turn
B
Same final state: these two operations commute at this state.
Step A → Step B
A is checking the other flag; B is checking the other flag. Turn favors B.
At most one thread insideA is checking the turn; B is checking the other flag. Turn favors B.
At most one thread insideA is checking the turn; B is checking the turn. Turn favors B.
At most one thread insideStep B → Step A
A is checking the other flag; B is checking the other flag. Turn favors B.
At most one thread insideA is checking the other flag; B is checking the turn. Turn favors B.
At most one thread insideA is checking the turn; B is checking the turn. Turn favors B.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
true- flag[B]
true- turn
A
Same final state: these two operations commute at this state.
Step A → Step B
A is checking the other flag; B is checking the turn. Turn favors A.
At most one thread insideA is checking the turn; B is checking the turn. Turn favors A.
At most one thread insideA is checking the turn; B is checking the other flag. Turn favors A.
At most one thread insideStep B → Step A
A is checking the other flag; B is checking the turn. Turn favors A.
At most one thread insideA is checking the other flag; B is checking the other flag. Turn favors A.
At most one thread insideA is checking the turn; B is checking the other flag. Turn favors A.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
true- flag[B]
true- turn
B
Same final state: these two operations commute at this state.
Step A → Step B
A is checking the other flag; B is checking the turn. Turn favors B.
At most one thread insideA is checking the turn; B is checking the turn. Turn favors B.
At most one thread insideA is checking the turn; B is inside the critical section. Turn favors B.
At most one thread insideStep B → Step A
A is checking the other flag; B is checking the turn. Turn favors B.
At most one thread insideA is checking the other flag; B is inside the critical section. Turn favors B.
At most one thread insideA is checking the turn; B is inside the critical section. Turn favors B.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
true- flag[B]
true- turn
A
Different final states: the order of these two operations matters here.
Step A → Step B
A is checking the other flag; B is inside the critical section. Turn favors A.
At most one thread insideA is checking the turn; B is inside the critical section. Turn favors A.
At most one thread insideA is checking the turn; B is idle. Turn favors A.
At most one thread insideStep B → Step A
A is checking the other flag; B is inside the critical section. Turn favors A.
At most one thread insideA is checking the other flag; B is idle. Turn favors A.
At most one thread insideA is inside the critical section; B is idle. Turn favors A.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
true- flag[B]
true- turn
B
Different final states: the order of these two operations matters here.
Step A → Step B
A is checking the other flag; B is inside the critical section. Turn favors B.
At most one thread insideA is checking the turn; B is inside the critical section. Turn favors B.
At most one thread insideA is checking the turn; B is idle. Turn favors B.
At most one thread insideStep B → Step A
A is checking the other flag; B is inside the critical section. Turn favors B.
At most one thread insideA is checking the other flag; B is idle. Turn favors B.
At most one thread insideA is inside the critical section; B is idle. Turn favors B.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
true- flag[B]
false- turn
A
Same final state: these two operations commute at this state.
Step A → Step B
A is checking the turn; B is idle. Turn favors A.
At most one thread insideA is inside the critical section; B is idle. Turn favors A.
At most one thread insideA is inside the critical section; B is holding its flag up. Turn favors A.
At most one thread insideStep B → Step A
A is checking the turn; B is idle. Turn favors A.
At most one thread insideA is checking the turn; B is holding its flag up. Turn favors A.
At most one thread insideA is inside the critical section; B is holding its flag up. Turn favors A.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
true- flag[B]
false- turn
B
Same final state: these two operations commute at this state.
Step A → Step B
A is checking the turn; B is idle. Turn favors B.
At most one thread insideA is checking the other flag; B is idle. Turn favors B.
At most one thread insideA is checking the other flag; B is holding its flag up. Turn favors B.
At most one thread insideStep B → Step A
A is checking the turn; B is idle. Turn favors B.
At most one thread insideA is checking the turn; B is holding its flag up. Turn favors B.
At most one thread insideA is checking the other flag; B is holding its flag up. Turn favors B.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
true- flag[B]
true- turn
A
Same final state: these two operations commute at this state.
Step A → Step B
A is checking the turn; B is holding its flag up. Turn favors A.
At most one thread insideA is inside the critical section; B is holding its flag up. Turn favors A.
At most one thread insideA is inside the critical section; B is checking the other flag. Turn favors A.
At most one thread insideStep B → Step A
A is checking the turn; B is holding its flag up. Turn favors A.
At most one thread insideA is checking the turn; B is checking the other flag. Turn favors A.
At most one thread insideA is inside the critical section; B is checking the other flag. Turn favors A.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
true- flag[B]
true- turn
B
Different final states: the order of these two operations matters here.
Step A → Step B
A is checking the turn; B is holding its flag up. Turn favors B.
At most one thread insideA is checking the other flag; B is holding its flag up. Turn favors B.
At most one thread insideA is checking the other flag; B is checking the other flag. Turn favors A.
At most one thread insideStep B → Step A
A is checking the turn; B is holding its flag up. Turn favors B.
At most one thread insideA is checking the turn; B is checking the other flag. Turn favors A.
At most one thread insideA is inside the critical section; B is checking the other flag. Turn favors A.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
true- flag[B]
true- turn
A
Same final state: these two operations commute at this state.
Step A → Step B
A is checking the turn; B is checking the other flag. Turn favors A.
At most one thread insideA is inside the critical section; B is checking the other flag. Turn favors A.
At most one thread insideA is inside the critical section; B is checking the turn. Turn favors A.
At most one thread insideStep B → Step A
A is checking the turn; B is checking the other flag. Turn favors A.
At most one thread insideA is checking the turn; B is checking the turn. Turn favors A.
At most one thread insideA is inside the critical section; B is checking the turn. Turn favors A.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
true- flag[B]
true- turn
B
Same final state: these two operations commute at this state.
Step A → Step B
A is checking the turn; B is checking the other flag. Turn favors B.
At most one thread insideA is checking the other flag; B is checking the other flag. Turn favors B.
At most one thread insideA is checking the other flag; B is checking the turn. Turn favors B.
At most one thread insideStep B → Step A
A is checking the turn; B is checking the other flag. Turn favors B.
At most one thread insideA is checking the turn; B is checking the turn. Turn favors B.
At most one thread insideA is checking the other flag; B is checking the turn. Turn favors B.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
true- flag[B]
true- turn
A
Same final state: these two operations commute at this state.
Step A → Step B
A is checking the turn; B is checking the turn. Turn favors A.
At most one thread insideA is inside the critical section; B is checking the turn. Turn favors A.
At most one thread insideA is inside the critical section; B is checking the other flag. Turn favors A.
At most one thread insideStep B → Step A
A is checking the turn; B is checking the turn. Turn favors A.
At most one thread insideA is checking the turn; B is checking the other flag. Turn favors A.
At most one thread insideA is inside the critical section; B is checking the other flag. Turn favors A.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
true- flag[B]
true- turn
B
Same final state: these two operations commute at this state.
Step A → Step B
A is checking the turn; B is checking the turn. Turn favors B.
At most one thread insideA is checking the other flag; B is checking the turn. Turn favors B.
At most one thread insideA is checking the other flag; B is inside the critical section. Turn favors B.
At most one thread insideStep B → Step A
A is checking the turn; B is checking the turn. Turn favors B.
At most one thread insideA is checking the turn; B is inside the critical section. Turn favors B.
At most one thread insideA is checking the other flag; B is inside the critical section. Turn favors B.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
true- flag[B]
true- turn
A
Same final state: these two operations commute at this state.
Step A → Step B
A is checking the turn; B is inside the critical section. Turn favors A.
At most one thread insideA is inside the critical section; B is inside the critical section. Turn favors A.
Race: both threads are insideA is inside the critical section; B is idle. Turn favors A.
At most one thread insideStep B → Step A
A is checking the turn; B is inside the critical section. Turn favors A.
At most one thread insideA is checking the turn; B is idle. Turn favors A.
At most one thread insideA is inside the critical section; B is idle. Turn favors A.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
true- flag[B]
true- turn
B
Same final state: these two operations commute at this state.
Step A → Step B
A is checking the turn; B is inside the critical section. Turn favors B.
At most one thread insideA is checking the other flag; B is inside the critical section. Turn favors B.
At most one thread insideA is checking the other flag; B is idle. Turn favors B.
At most one thread insideStep B → Step A
A is checking the turn; B is inside the critical section. Turn favors B.
At most one thread insideA is checking the turn; B is idle. Turn favors B.
At most one thread insideA is checking the other flag; B is idle. Turn favors B.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
true- flag[B]
false- turn
A
Same final state: these two operations commute at this state.
Step A → Step B
A is inside the critical section; B is idle. Turn favors A.
At most one thread insideA is idle; B is idle. Turn favors A.
At most one thread insideA is idle; B is holding its flag up. Turn favors A.
At most one thread insideStep B → Step A
A is inside the critical section; B is idle. Turn favors A.
At most one thread insideA is inside the critical section; B is holding its flag up. Turn favors A.
At most one thread insideA is idle; B is holding its flag up. Turn favors A.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
true- flag[B]
false- turn
B
Same final state: these two operations commute at this state.
Step A → Step B
A is inside the critical section; B is idle. Turn favors B.
At most one thread insideA is idle; B is idle. Turn favors B.
At most one thread insideA is idle; B is holding its flag up. Turn favors B.
At most one thread insideStep B → Step A
A is inside the critical section; B is idle. Turn favors B.
At most one thread insideA is inside the critical section; B is holding its flag up. Turn favors B.
At most one thread insideA is idle; B is holding its flag up. Turn favors B.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
true- flag[B]
true- turn
A
Same final state: these two operations commute at this state.
Step A → Step B
A is inside the critical section; B is holding its flag up. Turn favors A.
At most one thread insideA is idle; B is holding its flag up. Turn favors A.
At most one thread insideA is idle; B is checking the other flag. Turn favors A.
At most one thread insideStep B → Step A
A is inside the critical section; B is holding its flag up. Turn favors A.
At most one thread insideA is inside the critical section; B is checking the other flag. Turn favors A.
At most one thread insideA is idle; B is checking the other flag. Turn favors A.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
true- flag[B]
true- turn
B
Same final state: these two operations commute at this state.
Step A → Step B
A is inside the critical section; B is holding its flag up. Turn favors B.
At most one thread insideA is idle; B is holding its flag up. Turn favors B.
At most one thread insideA is idle; B is checking the other flag. Turn favors A.
At most one thread insideStep B → Step A
A is inside the critical section; B is holding its flag up. Turn favors B.
At most one thread insideA is inside the critical section; B is checking the other flag. Turn favors A.
At most one thread insideA is idle; B is checking the other flag. Turn favors A.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
true- flag[B]
true- turn
A
Different final states: the order of these two operations matters here.
Step A → Step B
A is inside the critical section; B is checking the other flag. Turn favors A.
At most one thread insideA is idle; B is checking the other flag. Turn favors A.
At most one thread insideA is idle; B is inside the critical section. Turn favors A.
At most one thread insideStep B → Step A
A is inside the critical section; B is checking the other flag. Turn favors A.
At most one thread insideA is inside the critical section; B is checking the turn. Turn favors A.
At most one thread insideA is idle; B is checking the turn. Turn favors A.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
true- flag[B]
true- turn
B
Different final states: the order of these two operations matters here.
Step A → Step B
A is inside the critical section; B is checking the other flag. Turn favors B.
At most one thread insideA is idle; B is checking the other flag. Turn favors B.
At most one thread insideA is idle; B is inside the critical section. Turn favors B.
At most one thread insideStep B → Step A
A is inside the critical section; B is checking the other flag. Turn favors B.
At most one thread insideA is inside the critical section; B is checking the turn. Turn favors B.
At most one thread insideA is idle; B is checking the turn. Turn favors B.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
true- flag[B]
true- turn
A
Same final state: these two operations commute at this state.
Step A → Step B
A is inside the critical section; B is checking the turn. Turn favors A.
At most one thread insideA is idle; B is checking the turn. Turn favors A.
At most one thread insideA is idle; B is checking the other flag. Turn favors A.
At most one thread insideStep B → Step A
A is inside the critical section; B is checking the turn. Turn favors A.
At most one thread insideA is inside the critical section; B is checking the other flag. Turn favors A.
At most one thread insideA is idle; B is checking the other flag. Turn favors A.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
true- flag[B]
true- turn
B
Same final state: these two operations commute at this state.
Step A → Step B
A is inside the critical section; B is checking the turn. Turn favors B.
At most one thread insideA is idle; B is checking the turn. Turn favors B.
At most one thread insideA is idle; B is inside the critical section. Turn favors B.
At most one thread insideStep B → Step A
A is inside the critical section; B is checking the turn. Turn favors B.
At most one thread insideA is inside the critical section; B is inside the critical section. Turn favors B.
Race: both threads are insideA is idle; B is inside the critical section. Turn favors B.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
true- flag[B]
true- turn
A
Same final state: these two operations commute at this state.
Step A → Step B
A is inside the critical section; B is inside the critical section. Turn favors A.
Race: both threads are insideA is idle; B is inside the critical section. Turn favors A.
At most one thread insideA is idle; B is idle. Turn favors A.
At most one thread insideStep B → Step A
A is inside the critical section; B is inside the critical section. Turn favors A.
Race: both threads are insideA is inside the critical section; B is idle. Turn favors A.
At most one thread insideA is idle; B is idle. Turn favors A.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Thread A
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
Thread B
- 0
raise my flag - 1
give the other thread priority - 2
read the other flag - 3
read turn; enter or retry - 4
critical section; then leave
- flag[A]
true- flag[B]
true- turn
B
Same final state: these two operations commute at this state.
Step A → Step B
A is inside the critical section; B is inside the critical section. Turn favors B.
Race: both threads are insideA is idle; B is inside the critical section. Turn favors B.
At most one thread insideA is idle; B is idle. Turn favors B.
At most one thread insideStep B → Step A
A is inside the critical section; B is inside the critical section. Turn favors B.
Race: both threads are insideA is inside the critical section; B is idle. Turn favors B.
At most one thread insideA is idle; B is idle. Turn favors B.
At most one thread insideLean computed both paths from this state. This compares two operations, not whole executions or a liveness property.
Step 0. A is idle; B is idle. Turn favors A.
Static diagram. Compiled Lean becomes available when browser support is enabled.
No compiled transitions have executed.
Order can matter without a race
Reset Peterson's explorer, then choose Step A and Step B once each. Both flags are now raised. Open Compare operation order. The two paths ask what happens if A takes its next step before B, or B before A.
The final states differ. Both operations write turn, so the last writer gives
the other thread priority. The order decides which thread waits; it does not
break mutual exclusion. Lean proves both facts about these concrete paths:
GwernPort.Examples.Mutex.Peterson.priority_order_mattersPeterson.step (Peterson.step Peterson.contending 0) 1 ≠
Peterson.step (Peterson.step Peterson.contending 1) 0Axioms: propext, Classical.choice, Quot.sound
GwernPort.Examples.Mutex.Peterson.both_priority_orders_safePeterson.Invariant (Peterson.step (Peterson.step Peterson.contending 0) 1) ∧
Peterson.Invariant (Peterson.step (Peterson.step Peterson.contending 1) 0)Axioms: propext, Classical.choice, Quot.sound
You can compare the two orders at any state in either explorer. Sometimes they commute: both paths arrive at exactly the same state. Sometimes they do not. The comparison follows the transition graph already computed by Lean, including an attempted blocked operation that leaves its state unchanged. It does not reimplement the algorithm in the browser.
The diagram is connected to the model by another theorem: for every model state and both choices of operation, its two-step endpoint is the identifier of the state obtained by executing those two model steps. The adapter source and theorem are included below.
Commutativity is local here: two particular operations from one starting state. It is a different question from whether every execution is safe. An algorithm can need ordering to arbitrate access while preserving its invariant throughout.
From a finite check to every schedule
There are five program-counter positions for each thread and two values of
turn: 50 states, with two possible actors per step. Lean checks a stronger
invariant across all 100 state-and-actor pairs. The invariant says:
both threads are never critical at once;
if A is critical and B is waiting, the turn favors A;
if B is critical and A is waiting, the turn favors B.
The initial state satisfies it. Every step preserves it. Induction over reachable states then covers schedules of any finite length. The theorem is not bounded by the number of clicks in the explorer.
GwernPort.Examples.Mutex.Peterson.every_schedule_safe∀ (schedule : List Thread), Peterson.Safe (Peterson.run schedule)Axioms: propext, Classical.choice, Quot.sound
The finite check uses decide; Lean's kernel checks the resulting proof term.
The authoring component rejects unfinished proofs and the pinned toolchain's
native-evaluation proof axiom. The models also prove that their numeric state
identifiers round-trip through the enumerated state inventory.
Lean in your browser
The diagrams describe states using small numbers. The mathematical model uses bounded counters: a program counter cannot name a nonexistent instruction. The compiled entry point takes two machine words, a state number and an actor, and returns the next state number. Both call the same pure Lean transition function.
Lean proves that these two representations agree after any finite schedule:
GwernPort.Examples.Mutex.KernelProofs.peterson_every_schedule_agrees∀ (schedule : List Thread),
KernelProofs.run GwernPort.Browser.MutexKernel.petersonStep 0 schedule =
(Peterson.stateId (Peterson.run schedule)).toUInt32Axioms: propext, Classical.choice, Quot.sound
The scalar Lean execution therefore inherits the safety theorem:
GwernPort.Examples.Mutex.KernelProofs.peterson_every_schedule_safe∀ (schedule : List Thread),
KernelProofs.SafeCode
(KernelProofs.run GwernPort.Browser.MutexKernel.petersonStep 0 schedule)Axioms: propext, Classical.choice, Quot.sound
The compiled module is 567 bytes. Lean emits C, then a WebAssembly toolchain retains the scalar functions. These functions need no heap allocation, runtime imports, or module initialization. This is a small compiled Lean program; it does not include a general Lean evaluator or proof checker in the browser.
Before enabling compiled mode, the browser checks the module's checksum and every transition against the diagram. Each subsequent click calls the compiled function and checks its destination. The status below each explorer records which mode is active and how many transitions your controls have executed. Undo and reset move through your history; the example schedule executes its steps again. Order comparisons are diagrams computed by Lean at build time.
If WebAssembly is unavailable or a check fails, the explorer labels itself Static diagram and follows the graph that Lean rendered at build time. The essay, proofs, and initial diagrams remain readable without JavaScript.
The theorems establish correspondence between Lean definitions. An independent execution check tests all 136 valid state-and-actor combinations in the produced module, 88 invalid inputs, and 8,192 additional schedule steps. Those checks do not prove the compiler toolchain or the browser correct.
What this model says
This is a sequentially consistent interleaving model: every selected operation happens atomically, and the two flags are derived from the program counters. It proves mutual exclusion in that model. It does not establish fairness, termination, a particular CPU's memory-ordering behavior, or the correctness of the browser. Those are separate specifications.
That separation is useful. The model, its proof, the diagrams, and the examples share one source. A small browser binding provides the interaction. Verso lets the explanation sit beside the definitions that make it true.
The algorithm is from Gary L. Peterson's “Myths about the mutual exclusion problem” (1981). The site's complete model and proofs are included below, so you can inspect the definitions without needing an account or access to the repository. The source display is read from the same imported Lean file at compile time.
Read the model
The definition step is the entire transition system. Start with Safe, follow
Invariant and step_invariant, then read the short induction that reaches
every_schedule_safe. The second namespace contains the deliberately broken
algorithm and its counterexample.
Open the complete Lean source¶
/- GwernPort/Examples/Mutex/Core.lean -/
namespace GwernPort.Examples.Mutex.Core
/-- Exact shared transition source for the essay's source display. -/
def sourceText : String := include_str "Core.lean"
/-- One Peterson operation. `false` denotes A and `true` denotes B.
The caller chooses the counter representation and how to return the result.
An inline result constructor also permits an allocation-free scalar export. -/
@[inline]
def peterson {Pc Result : Type} [BEq Pc]
[OfNat Pc 0] [OfNat Pc 1] [OfNat Pc 2] [OfNat Pc 3] [OfNat Pc 4]
(a b : Pc) (turn actor : Bool) (emit : Pc → Pc → Bool → Result) : Result :=
if !actor then
if a == 0 then emit 1 b turn
else if a == 1 then emit 2 b true
else if a == 2 then emit (if b == 0 then 4 else 3) b turn
else if a == 3 then emit (if !turn then 4 else 2) b turn
else emit 0 b turn
else
if b == 0 then emit a 1 turn
else if b == 1 then emit a 2 false
else if b == 2 then emit a (if a == 0 then 4 else 3) turn
else if b == 3 then emit a (if turn then 4 else 2) turn
else emit a 0 turn
/-- One deliberately non-atomic test-then-set operation, with the same result
constructor boundary as Peterson. The separate test and write admit a race. -/
@[inline]
def naive {Pc Result : Type} [BEq Pc] [OfNat Pc 0] [OfNat Pc 1] [OfNat Pc 2]
(a b : Pc) (locked actor : Bool) (emit : Pc → Pc → Bool → Result) : Result :=
if !actor then
if a == 0 then emit (if locked then a else 1) b locked
else if a == 1 then emit 2 b true
else emit 0 b false
else
if b == 0 then emit a (if locked then b else 1) locked
else if b == 1 then emit a 2 true
else emit a 0 false
end GwernPort.Examples.Mutex.Core
/- GwernPort/Examples/Mutex.lean -/
import GwernPort.Examples.Mutex.Core
/-!
Two small sequentially consistent interleaving models. Each step is atomic;
the browser later selects among transitions computed from these definitions.
-/
namespace GwernPort.Examples.Mutex
/-- The module carries its own exact source into essays that import it.
Even a comment-only edit changes this value and invalidates dependent pages. -/
def sourceText : String :=
"/- GwernPort/Examples/Mutex/Core.lean -/\n" ++ Core.sourceText ++
"\n\n/- GwernPort/Examples/Mutex.lean -/\n" ++ include_str "Mutex.lean"
abbrev Thread := Fin 2
namespace Peterson
/-- 0 = idle, 1 = raised flag, 2 = read other flag, 3 = read turn,
4 = critical section. The guard's two loads are separate atomic steps.
A flag is true exactly when its thread is not idle. -/
structure State where
a : Fin 5
b : Fin 5
turn : Thread
deriving DecidableEq, Repr, Inhabited
def initial : State := ⟨0, 0, 0⟩
def stateId (s : State) : Nat := s.a.val * 10 + s.b.val * 2 + s.turn.val
/-- One atomic operation by one thread, including a stuttering blocked wait. -/
@[inline]
def step (s : State) (thread : Thread) : State :=
Core.peterson s.a s.b (s.turn == 1) (thread == 1)
(fun a b turn => ⟨a, b, if turn then 1 else 0⟩)
def Safe (s : State) : Prop := ¬ (s.a = 4 ∧ s.b = 4)
/-- The turn constraint prevents a waiting thread from joining a critical one. -/
def Invariant (s : State) : Prop :=
Safe s ∧
(s.a = 4 → s.b = 2 ∨ s.b = 3 → s.turn = 0) ∧
(s.b = 4 → s.a = 2 ∨ s.a = 3 → s.turn = 1)
instance (s : State) : Decidable (Safe s) := inferInstanceAs (Decidable (¬ (s.a = 4 ∧ s.b = 4)))
instance (s : State) : Decidable (Invariant s) :=
inferInstanceAs (Decidable (Safe s ∧
(s.a = 4 → s.b = 2 ∨ s.b = 3 → s.turn = 0) ∧ (s.b = 4 → s.a = 2 ∨ s.a = 3 → s.turn = 1)))
/-- A finite kernel computation checks all 100 state/actor pairs. -/
theorem step_invariant : ∀ (a b : Fin 5) (turn actor : Thread),
Invariant ⟨a, b, turn⟩ → Invariant (step ⟨a, b, turn⟩ actor) := by
decide
inductive Reachable : State → Prop where
| initial : Reachable initial
| advance (s : State) (actor : Thread) : Reachable s → Reachable (step s actor)
theorem reachable_invariant {s : State} (h : Reachable s) : Invariant s := by
induction h with
| initial => decide
| advance state actor _ ih =>
cases state with
| mk a b turn => exact step_invariant a b turn actor ih
/-- Every reachable state is safe, regardless of the number of scheduled steps. -/
theorem mutual_exclusion {s : State} (h : Reachable s) : Safe s :=
(reachable_invariant h).1
def run (schedule : List Thread) : State := schedule.foldl step initial
theorem run_reachable (schedule : List Thread) : Reachable (run schedule) := by
have general : ∀ (events : List Thread) (s : State), Reachable s →
Reachable (events.foldl step s) := by
intro events
induction events with
| nil => intro s h; exact h
| cons actor rest ih =>
intro s h
exact ih (step s actor) (.advance s actor h)
exact general schedule initial .initial
theorem every_schedule_safe (schedule : List Thread) : Safe (run schedule) :=
mutual_exclusion (run_reachable schedule)
/-- Both actors raised their flags and are about to give each other priority. -/
def contending : State := run [0, 1]
/-- The last priority write changes which actor waits. Order dependence is
not itself a safety failure: both concrete results still satisfy the invariant. -/
theorem priority_order_matters :
step (step contending 0) 1 ≠ step (step contending 1) 0 := by decide
theorem both_priority_orders_safe :
Invariant (step (step contending 0) 1) ∧
Invariant (step (step contending 1) 0) := by decide
end Peterson
namespace Naive
/-- 0 = ready to test the lock, 1 = observed free, 2 = critical section. -/
structure State where
a : Fin 3
b : Fin 3
locked : Bool
deriving DecidableEq, Repr, Inhabited
def initial : State := ⟨0, 0, false⟩
def stateId (s : State) : Nat := s.a.val * 6 + s.b.val * 2 + if s.locked then 1 else 0
@[inline]
def step (s : State) (thread : Thread) : State :=
Core.naive s.a s.b s.locked (thread == 1) (fun a b locked => ⟨a, b, locked⟩)
def run (schedule : List Thread) : State := schedule.foldl step initial
def race : List Thread := [0, 1, 0, 1]
/-- Two separate reads can both see an unlocked lock before either write. -/
theorem counterexample : (run race).a = 2 ∧ (run race).b = 2 := by
constructor <;> rfl
end Naive
end GwernPort.Examples.Mutex
Inspect the diagram's connection to the model¶
The diagram follows graph edges; this theorem checks that their endpoints agree
with the model's step. It does not prove the browser's display code correct.
GwernPort.Examples.Mutex.Peterson.order_path_matches_model∀ (a b : Fin 5) (turn first second : Thread),
Option.map (fun x => x.final)
(Peterson.machine.twoStep? (Peterson.stateId { a := a, b := b, turn := turn })
↑first ↑second) =
some
(Peterson.stateId
(Peterson.step (Peterson.step { a := a, b := b, turn := turn } first) second))Axioms: propext, Classical.choice, Quot.sound
import GwernPort.Examples.Mutex
import GwernPort.Verso.Components.Machine
namespace GwernPort.Examples.Mutex
open GwernPort.Verso
/-- Public adapter source with normal module dependency invalidation. -/
def viewSourceText : String := include_str "MutexView.lean"
private def name (thread : Thread) : String := if thread == 0 then "A" else "B"
def trace {S : Type} (step : S → Thread → S) (initial : S) : List Thread → List S
| [] => [initial]
| actor :: rest => initial :: trace step (step initial actor) rest
namespace Peterson
def states : Array State := ((List.finRange 5).flatMap fun a =>
(List.finRange 5).flatMap fun b =>
(List.finRange 2).map fun turn => State.mk a b turn).toArray
theorem inventory_roundtrip : ∀ (a b : Fin 5) (turn : Thread),
states[stateId ⟨a, b, turn⟩]? = some ⟨a, b, turn⟩ := by decide
private def location (pc : Fin 5) : String :=
#["idle", "holding its flag up", "checking the other flag", "checking the turn", "inside the critical section"][pc.val]!
private def lane (thread : Thread) (pc : Fin 5) : MachineLane := {
name := s!"Thread {name thread}"
program := #["raise my flag", "give the other thread priority", "read the other flag", "read turn; enter or retry", "critical section; then leave"]
current := pc.val
critical := pc == 4
}
def view (s : State) : MachineState := {
description := s!"A is {location s.a}; B is {location s.b}. Turn favors {name s.turn}."
lanes := #[lane 0 s.a, lane 1 s.b]
facts := #[("flag[A]", toString (s.a != 0)), ("flag[B]", toString (s.b != 0)), ("turn", name s.turn)]
transitions := (#[0, 1] : Array Thread).map fun actor => {
label := s!"Step {name actor}"
target := stateId (step s actor)
enabled := step s actor != s
}
safe := decide (Safe s)
status := if decide (Safe s) then "At most one thread inside" else "Race: both threads are inside"
}
def machine : Machine := {
title := "Peterson's algorithm: try any schedule"
compareActors := some (0, 1)
states := states.map view
initial := stateId initial
exampleTrace := (trace step initial [0, 1, 0, 1, 0, 1, 0, 1, 0, 1]).toArray.map stateId
exampleLabel := "Run a contended schedule"
}
/-- Every two-operation diagram endpoint agrees with two actual model steps. -/
theorem order_path_matches_model : ∀ (a b : Fin 5) (turn first second : Thread),
((machine.twoStep? (stateId ⟨a, b, turn⟩) first.val second.val).map (·.final)) =
some (stateId (step (step ⟨a, b, turn⟩ first) second)) := by decide +kernel
end Peterson
namespace Naive
def states : Array State := ((List.finRange 3).flatMap fun a =>
(List.finRange 3).flatMap fun b =>
[State.mk a b false, State.mk a b true]).toArray
theorem inventory_roundtrip : ∀ (a b : Fin 3) (locked : Bool),
states[stateId ⟨a, b, locked⟩]? = some ⟨a, b, locked⟩ := by decide
private def location (pc : Fin 3) : String :=
#["ready to check", "convinced the lock is free", "inside the critical section"][pc.val]!
private def lane (thread : Thread) (pc : Fin 3) : MachineLane := {
name := s!"Thread {name thread}"
program := #["check whether the lock is free", "set locked = true and enter", "critical section; then unlock"]
current := pc.val
critical := pc == 2
}
def view (s : State) : MachineState := {
description := s!"A is {location s.a}; B is {location s.b}."
lanes := #[lane 0 s.a, lane 1 s.b]
facts := #[("locked", toString s.locked)]
transitions := (#[0, 1] : Array Thread).map fun actor => {
label := s!"Step {name actor}"
target := stateId (step s actor)
enabled := step s actor != s
}
safe := !(s.a == 2 && s.b == 2)
status := if s.a == 2 && s.b == 2 then "Race: both threads are inside" else "At most one thread inside"
}
def machine : Machine := {
title := "A naive lock: can you make both threads enter?"
compareActors := some (0, 1)
states := states.map view
initial := stateId initial
exampleTrace := (trace step initial race).toArray.map stateId
exampleLabel := "Show the four-step race"
}
theorem order_path_matches_model : ∀ (a b : Fin 3) (locked : Bool) (first second : Thread),
((machine.twoStep? (stateId ⟨a, b, locked⟩) first.val second.val).map (·.final)) =
some (stateId (step (step ⟨a, b, locked⟩ first) second)) := by decide +kernel
end Naive
end GwernPort.Examples.Mutex
Inspect the compiled boundary and its proofs¶
import GwernPort.Examples.Mutex.Core
namespace GwernPort.Browser.MutexKernel
open GwernPort.Examples.Mutex
-- Retained exports must not depend on module-initialized closed values.
set_option compiler.extract_closed false
/-- Scalar ABI version. The argument keeps the export a function. -/
@[export gwernport_mutex_abi]
def abiVersion (_ : UInt32) : UInt32 := 1
/-- Return the next existing Peterson state ID, or `0xffffffff` for an invalid
state/actor. Both model and export execute `Core.peterson`. -/
@[export gwernport_peterson_step]
def petersonStep (code actor : UInt32) : UInt32 :=
if code >= 50 || actor >= 2 then 4294967295
else
Core.peterson (code / 10).toUInt8 ((code / 2) % 5).toUInt8
(code % 2 == 1) (actor == 1)
(fun a b turn => a.toUInt32 * 10 + b.toUInt32 * 2 + if turn then 1 else 0)
/-- Return the next naive-lock state ID, with the same explicit invalid-input
sentinel. Both model and export execute `Core.naive`. -/
@[export gwernport_naive_step]
def naiveStep (code actor : UInt32) : UInt32 :=
if code >= 18 || actor >= 2 then 4294967295
else
Core.naive (code / 6).toUInt8 ((code / 2) % 3).toUInt8
(code % 2 == 1) (actor == 1)
(fun a b locked => a.toUInt32 * 6 + b.toUInt32 * 2 + if locked then 1 else 0)
end GwernPort.Browser.MutexKernel
import GwernPort.Examples.Mutex
import GwernPort.Browser.MutexKernel
namespace GwernPort.Examples.Mutex.KernelProofs
open GwernPort.Browser.MutexKernel
/-- The Lean scalar entry point agrees with every typed Peterson state and actor.
This is kernel computation, not a native-evaluation proof axiom. -/
private theorem petersonAll : ∀ (a b : Fin 5) (turn actor : Thread),
petersonStep (Peterson.stateId ⟨a, b, turn⟩).toUInt32 actor.val.toUInt32 =
(Peterson.stateId (Peterson.step ⟨a, b, turn⟩ actor)).toUInt32 := by
decide
theorem peterson_step_agrees (state : Peterson.State) (actor : Thread) :
petersonStep (Peterson.stateId state).toUInt32 actor.val.toUInt32 =
(Peterson.stateId (Peterson.step state actor)).toUInt32 := by
cases state with
| mk a b turn => exact petersonAll a b turn actor
private theorem naiveAll : ∀ (a b : Fin 3) (locked : Bool) (actor : Thread),
naiveStep (Naive.stateId ⟨a, b, locked⟩).toUInt32 actor.val.toUInt32 =
(Naive.stateId (Naive.step ⟨a, b, locked⟩ actor)).toUInt32 := by
decide
theorem naive_step_agrees (state : Naive.State) (actor : Thread) :
naiveStep (Naive.stateId state).toUInt32 actor.val.toUInt32 =
(Naive.stateId (Naive.step state actor)).toUInt32 := by
cases state with
| mk a b locked => exact naiveAll a b locked actor
def run (step : UInt32 → UInt32 → UInt32) (state : UInt32) : List Thread → UInt32
| [] => state
| actor :: rest => run step (step state actor.val.toUInt32) rest
theorem peterson_schedule_from (state : Peterson.State) (schedule : List Thread) :
run petersonStep (Peterson.stateId state).toUInt32 schedule =
(Peterson.stateId (schedule.foldl Peterson.step state)).toUInt32 := by
induction schedule generalizing state with
| nil => rfl
| cons actor rest ih =>
simp only [run, List.foldl_cons]
rw [peterson_step_agrees]
exact ih (Peterson.step state actor)
theorem naive_schedule_from (state : Naive.State) (schedule : List Thread) :
run naiveStep (Naive.stateId state).toUInt32 schedule =
(Naive.stateId (schedule.foldl Naive.step state)).toUInt32 := by
induction schedule generalizing state with
| nil => rfl
| cons actor rest ih =>
simp only [run, List.foldl_cons]
rw [naive_step_agrees]
exact ih (Naive.step state actor)
/-- Equality of the two Lean executions for schedules of any finite length. -/
theorem peterson_every_schedule_agrees (schedule : List Thread) :
run petersonStep 0 schedule = (Peterson.stateId (Peterson.run schedule)).toUInt32 :=
peterson_schedule_from Peterson.initial schedule
theorem naive_every_schedule_agrees (schedule : List Thread) :
run naiveStep 0 schedule = (Naive.stateId (Naive.run schedule)).toUInt32 :=
naive_schedule_from Naive.initial schedule
def SafeCode (code : UInt32) : Prop :=
¬ (code / 10 = 4 ∧ (code / 2) % 5 = 4)
private theorem safety_encoding : ∀ (a b : Fin 5) (turn : Thread),
Peterson.Safe ⟨a, b, turn⟩ ↔ SafeCode (Peterson.stateId ⟨a, b, turn⟩).toUInt32 := by
unfold SafeCode
decide
/-- The scalar Lean execution inherits the original arbitrary-schedule theorem.
Compilation and browser execution are separate evidence boundaries. -/
theorem peterson_every_schedule_safe (schedule : List Thread) :
SafeCode (run petersonStep 0 schedule) := by
rw [peterson_every_schedule_agrees]
have h := Peterson.every_schedule_safe schedule
cases stateEq : Peterson.run schedule with
| mk a b turn =>
rw [stateEq] at h
exact (safety_encoding a b turn).mp h
theorem naive_race_reaches_both : run naiveStep 0 Naive.race = 17 := by decide
theorem peterson_rejects (state actor : UInt32)
(invalid : (state >= 50 || actor >= 2) = true) :
petersonStep state actor = 4294967295 := by
simp [petersonStep, invalid]
theorem naive_rejects (state actor : UInt32)
(invalid : (state >= 18 || actor >= 2) = true) :
naiveStep state actor = 4294967295 := by
simp [naiveStep, invalid]
end GwernPort.Examples.Mutex.KernelProofs
For more about writing essays this way, see writing with executable Lean examples.