Two Threads, One Door

Break a naive lock, explore Peterson's algorithm, and inspect the Lean proof behind the page.

Alok Singh·1164 words

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.

A naive lock: can you make both threads enter?
At most one thread inside

Thread A

  1. 0check whether the lock is free
  2. 1set locked = true and enter
  3. 2critical section; then unlock

Thread B

  1. 0check whether the lock is free
  2. 1set locked = true and enter
  3. 2critical section; then unlock
locked
false

Step 0. A is ready to check; B is ready to check.

Static diagram. Compiled Lean becomes available when browser support is enabled.

The failure is a concrete Lean value. Changing the transition function changes this result, the explorer, and the theorem obligation together.

Evaluated by Lean
(Naive.run Naive.race)
Result
{ a := 2, b := 2, locked := true }
Checked by Lean's kernel
GwernPort.Examples.Mutex.Naive.counterexample
(Naive.run Naive.race).a = 2 ∧ (Naive.run Naive.race).b = 2

Axioms: 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.

Peterson's algorithm: try any schedule
At most one thread inside

Thread A

  1. 0raise my flag
  2. 1give the other thread priority
  3. 2read the other flag
  4. 3read turn; enter or retry
  5. 4critical section; then leave

Thread B

  1. 0raise my flag
  2. 1give the other thread priority
  3. 2read the other flag
  4. 3read turn; enter or retry
  5. 4critical section; then leave
flag[A]
false
flag[B]
false
turn
A

Step 0. A is idle; B is idle. Turn favors A.

Static diagram. Compiled Lean becomes available when browser support is enabled.

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:

Checked by Lean's kernel
GwernPort.Examples.Mutex.Peterson.priority_order_matters
Peterson.step (Peterson.step Peterson.contending 0) 1 ≠
  Peterson.step (Peterson.step Peterson.contending 1) 0

Axioms: propext, Classical.choice, Quot.sound

Checked by Lean's kernel
GwernPort.Examples.Mutex.Peterson.both_priority_orders_safe
Peterson.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.

Checked by Lean's kernel
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:

Checked by Lean's kernel
GwernPort.Examples.Mutex.KernelProofs.peterson_every_schedule_agrees
∀ (schedule : List Thread),
  KernelProofs.run GwernPort.Browser.MutexKernel.petersonStep 0 schedule =
    (Peterson.stateId (Peterson.run schedule)).toUInt32

Axioms: propext, Classical.choice, Quot.sound

The scalar Lean execution therefore inherits the safety theorem:

Checked by Lean's kernel
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
Complete Lean model and proofs
/- 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.

Checked by Lean's kernel
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

Complete Lean model-to-diagram adapter
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
Scalar Lean entry points compiled to WebAssembly
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
Complete model-to-scalar correspondence proofs
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.