Research / 2026

Many writers, one main line

Draft · the definitions and theorems on this page are machine-checked in Lean; independent review is in progress.

Many autonomous agents change one shared state at once. Declared footprints, time-bounded leases, a batching merge queue that bisects on failure, and task groupings with prerequisites combine into one admission protocol. A Lean proof shows that the main line only ever holds checked states, that no admitted change is lost, that disjoint work never conflicts, and how many check runs a drain costs.

Merge queuesGroup testingLeasesOptimistic validation
1 + 2k·d
check runs, in the separable fault model, to drain a batch of at most 2^d changes of which k are faulty; one-at-a-time admission runs the checks once per change
0 lost
every admitted change either lands on the main line or comes back with a reason, at every bisection depth and for every check
1 run
a pairwise-disjoint batch whose members are all ready on the main line and that passes the checks lands in full in one run, and every queue order reaches the same state

Picture a few dozen autonomous agents working on one repository at the same time. Each takes a task, edits some files, runs what it can locally and asks for its change to be merged. The main line is shared. If changes go in one at a time, each followed by a full run of the checks, the queue is safe but slow, and it gets slower with every agent added. If changes go in without checks, the main line soon holds a state that nobody tested. Two agents can also pick the same task, or edit the same file from two different starting points.

None of the parts used here is new. Declaring what a change reads and writes, validating it at commit time, granting time-bounded exclusive claims, testing a pool of items at once and splitting the pool when it fails, and ordering tasks by their prerequisites are all known techniques, and each is credited below. The point of this article is the combination. I state the goal precisely, put the parts together into one protocol, and prove that the protocol achieves the goal.

All Lean below is core Lean 4 (checked with 4.16.0). The code blocks, joined in order, form one file that compiles with no errors, no warnings and no sorry, admit or added axiom. #print axioms on the theorems shows only the standard axioms that simp and omega use (propext, Quot.sound, Classical.choice). The concrete checks at the end are evaluated by the kernel with decide, so they add no axiom either.

The goal

There is one main line. Agents submit changes to it. A check is a Boolean verdict on a state of the main line: the build, the test suite, whatever the project runs before it accepts a state. A change is admitted once it enters the queue. I want six things.

Goal.

  1. Gate. Every state the main line ever holds passed the checks, provided the starting state did.
  2. No loss. Every admitted change either lands on the main line exactly once, in queue order, or is handed back to its author with a reason. The reason is evidence: a change handed back as failing did fail the checks, and one handed back as stale did not apply.
  3. Disjoint work never conflicts. Two changes whose declared footprints share no key never make each other stale, and the order in which they land does not change the result.
  4. Exclusive claims. Two different agents never hold the claim on the same task at the same time.
  5. Consistent plans. Tasks are grouped into milestones and plans, and prerequisites can be declared at all three levels. The grouped prerequisites are acyclic exactly when a schedule respecting them exists, given positive durations, unique task identifiers and no prerequisites on empty groups, and that can be decided from tasks alone under a stated hypothesis.
  6. Progress and cost. Every drain of the queue consumes its whole batch. When few changes are faulty, a drain runs the checks far fewer times than once per change.

Property 6 is about a single drain. Whether an agent whose change keeps coming back ever gets it in is a property of the agent, not of the queue, and the limits section returns to it.

The components

Declared footprints with validation at commit. Each change states the keys it touches, the values it expects to find there, and the values it writes. It lands only if every declared key still holds the expected value, which is a compare-and-swap on the footprint. This is the validation phase of “On Optimistic Methods for Concurrency Control” (ACM Transactions on Database Systems, 1981). The fact that operations with disjoint read and write sets commute is the condition of “Analysis of Programs for Parallel Processing” (IEEE Transactions on Electronic Computers, 1966).

Leases. A claim on a task is granted for a fixed time TT. The holder may renew it. Another agent may take it only after it has run out. This is the mechanism of “Leases: An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency” (SOSP 1989).

A batching queue with bisection. The queue tests a whole batch of changes with one run of the checks. If the batch passes, it lands in one step. If it fails, the queue splits it in two halves and drains each half the same way, down to single changes. This is group testing, from “The Detection of Defective Members of Large Populations” (Annals of Mathematical Statistics, 1943), with the binary splitting of “A Method for Detecting All Defective Members in a Population by Group Testing” (Journal of the American Statistical Association, 1972).

Prerequisite order over groupings. Tasks carry prerequisites, and so do the milestones and plans that group them. A schedule must start each task after everything it waits for has ended. A schedule of this kind exists for an acyclic order, as in “Topological Sorting of Large Networks” (Communications of the ACM, 1962).

The architecture

The protocol runs in a loop.

  1. Plan. The tasks, their milestones and plans, and the prerequisites at each level form a grouping. A task becomes eligible once every task, milestone and plan it waits for is complete.
  2. Claim. An agent asks the arbiter for a lease on an eligible task. While the lease is live, no other agent is granted it.
  3. Work. The agent produces a change and declares its footprint: the keys it read, with the values it saw, and the keys it writes, with the new values.
  4. Admit. The change enters the queue.
  5. Drain. The queue takes a batch. If every change in it applies in turn on the main line and the checks pass on the result, the whole batch lands as one new state of the main line. Otherwise the batch is split and each half is drained the same way. A single change is applied and checked on its own.
  6. Return. A change that did not land goes back to its author with a reason: conflict (it no longer applied) or red (alone on the main line, it failed the checks). The author can rebase and resubmit.

Each piece has its own job. Leases keep two agents off the same task. Footprints keep agents on different tasks out of each other’s way. The queue keeps every state of the main line checked while spending one run on many changes. The grouping keeps the plan executable.

The sections below define each component in Lean and prove its part of the goal. A final section puts the theorems side by side against the goal.

Footprints

A state maps keys to values, s:K→Vs : K \to V. A footprint ff consists of a finite list of keys keys(f)\mathrm{keys}(f) and two functions old(f),new(f):K→V\mathrm{old}(f), \mathrm{new}(f) : K \to V, of which only the values on keys(f)\mathrm{keys}(f) matter.

Ready, put, land. The change ff is ready on ss when s(k)=old(f)(k)s(k) = \mathrm{old}(f)(k) for every k∈keys(f)k \in \mathrm{keys}(f). Putting ff writes new(f)\mathrm{new}(f) on the declared keys and leaves every other key alone:

put(f,s)(k)={new(f)(k)k∈keys(f)s(k)otherwise.\mathrm{put}(f, s)(k) = \begin{cases} \mathrm{new}(f)(k) & k \in \mathrm{keys}(f) \\ s(k) & \text{otherwise.} \end{cases}

Landing is the compare-and-swap: land(s,f)=put(f,s)\mathrm{land}(s, f) = \mathrm{put}(f, s) if ff is ready on ss, and it fails otherwise. Two footprints are disjoint when no key is declared by both. Landing a list lands its members left to right and fails at the first one that is not ready.

A key that a change only reads appears in its footprint with new(f)(k)=old(f)(k)\mathrm{new}(f)(k) = \mathrm{old}(f)(k), so a read is a write of the value already there. This keeps the model to one list of keys per change.

set_option linter.unusedSectionVars false

/-! # 1. Footprints: declared reads and writes on a keyed state -/

namespace Footprint

/-- A change declares the keys it touches, the values it expects there, and the values it writes. -/
structure Fp (K V : Type) where
  keys : List K
  old  : K → V
  new  : K → V

variable {K V : Type} [DecidableEq K] [DecidableEq V]

/-- The change applies to `s`: every declared key still holds the expected value. -/
def Ready (f : Fp K V) (s : K → V) : Prop := ∀ k ∈ f.keys, s k = f.old k

instance (f : Fp K V) (s : K → V) : Decidable (Ready f s) := by
  unfold Ready; infer_instance

/-- Write the declared values, leave every other key alone. -/
def put (f : Fp K V) (s : K → V) : K → V := fun k => if k ∈ f.keys then f.new k else s k

/-- Landing a change: a compare-and-swap on its footprint. -/
def land (s : K → V) (f : Fp K V) : Option (K → V) := if Ready f s then some (put f s) else none

/-- Two footprints are disjoint when no key is declared by both. -/
def Disj (f g : Fp K V) : Prop := ∀ k ∈ f.keys, k ∉ g.keys

The first property is the one the goal names directly.

Theorem 1 (disjoint work never conflicts). If ff and gg are disjoint, then gg is ready on put(f,s)\mathrm{put}(f, s) exactly when it is ready on ss.

Proof. Every key of gg lies outside keys(f)\mathrm{keys}(f), and put\mathrm{put} leaves those keys unchanged. ∎

Commutation follows. Since landing can fail, the statement is about partial operations: both orders fail together, or both reach the same state.

Theorem 2 (order independence). For disjoint ff and gg, landing ff then gg gives the same result as landing gg then ff, failures included. Consequently, if a list of changes is pairwise disjoint, every permutation of it lands to the same result from every state.

Proof. The writes commute pointwise, because each key is written by at most one of the two. Readiness of the second change does not depend on whether the first has landed, by Theorem 1. For the list, induct on the derivation of the permutation: an adjacent swap is the two-change case, and the other steps keep pairwise disjointness. ∎

theorem disj_symm {f g : Fp K V} (h : Disj f g) : Disj g f :=
  fun k hg hf => h k hf hg

theorem put_frame {f : Fp K V} {s : K → V} {k : K} (hk : k ∉ f.keys) : put f s k = s k := by
  simp [put, hk]

/-- Disjoint work never conflicts: landing `f` leaves `g` exactly as applicable as before. -/
theorem ready_put_disj {f g : Fp K V} (h : Disj f g) (s : K → V) : Ready g (put f s) ↔ Ready g s := by
  constructor
  · intro hr k hk
    have := hr k hk
    rwa [put_frame (disj_symm h k hk)] at this
  · intro hr k hk
    rw [put_frame (disj_symm h k hk)]
    exact hr k hk

theorem put_comm {f g : Fp K V} (h : Disj f g) (s : K → V) : put f (put g s) = put g (put f s) := by
  funext k
  by_cases hf : k ∈ f.keys
  · have hg : k ∉ g.keys := h k hf
    simp [put, hf, hg]
  · by_cases hg : k ∈ g.keys <;> simp [put, hf, hg]

/-- Disjoint changes commute, as partial operations: both orders fail together or reach the same state. -/
theorem land_comm {f g : Fp K V} (h : Disj f g) (s : K → V) :
    (land s f).bind (fun t => land t g) = (land s g).bind (fun t => land t f) := by
  have e1 := ready_put_disj h s
  have e2 := ready_put_disj (disj_symm h) s
  unfold land
  by_cases hf : Ready f s <;> by_cases hg : Ready g s <;>
    simp [hf, hg, e1, e2, put_comm h]

/-- Land a list of changes left to right, stopping at the first one that does not apply. -/
def landAll : (K → V) → List (Fp K V) → Option (K → V)
  | s, [] => some s
  | s, f :: fs => (land s f).bind (fun t => landAll t fs)

theorem landAll_swap {f g : Fp K V} (h : Disj f g) (s : K → V) (l : List (Fp K V)) :
    landAll s (f :: g :: l) = landAll s (g :: f :: l) := by
  simp only [landAll]
  have := land_comm h s
  calc (land s f).bind (fun t => (land t g).bind (fun u => landAll u l))
        = ((land s f).bind (fun t => land t g)).bind (fun u => landAll u l) := by
          cases land s f <;> simp
    _ = ((land s g).bind (fun t => land t f)).bind (fun u => landAll u l) := by rw [this]
    _ = (land s g).bind (fun t => (land t f).bind (fun u => landAll u l)) := by
          cases land s g <;> simp

/-- ORDER INDEPENDENCE: pairwise-disjoint changes land to the same result in every order. -/
theorem landAll_perm {l l' : List (Fp K V)} (p : l.Perm l') :
    l.Pairwise Disj → ∀ s, landAll s l = landAll s l' := by
  induction p with
  | nil => intro _ s; rfl
  | cons x _ ih =>
    intro hp s
    simp only [landAll]
    have ih' := ih (List.pairwise_cons.mp hp).2
    cases land s x <;> simp [ih']
  | swap x y l =>
    intro hp s
    have hyx : Disj y x := (List.pairwise_cons.mp hp).1 x (List.mem_cons_self ..)
    exact landAll_swap hyx s l
  | trans p1 _ ih1 ih2 =>
    intro hp s
    rw [ih1 hp s, ih2 (hp.perm p1 disj_symm) s]

end Footprint

The merge queue

The queue is generic in what a change is. A state of the main line is its history, the list of changes landed so far, in order. Two parameters describe the world:

  • the check gg, a Boolean verdict on a history;
  • the applicability test clean(h,c)\mathrm{clean}(h, c), which says whether change cc applies on history hh.

A drain from main line hh on batch cscs returns the new main line, the list of every state the main line moved to, the changes handed back with their reasons, and the number of check runs.

Sequential admission (seq\mathrm{seq}) is the baseline. It takes one change cc at a time. If cc is not clean on hh, it is returned as conflict. Otherwise the checks run on h⋅ch \cdot c. If they pass, the main line moves to h⋅ch \cdot c; if not, cc is returned as red.

Bisection (bisn\mathrm{bis}_n, with depth budget nn) on a batch of at least two changes first asks whether every change applies in turn. If so, it runs the checks once on h⋅csh \cdot cs, and if they pass, the main line moves to h⋅csh \cdot cs in a single step. In every other case it splits cscs after its first ⌈∣cs∣/2⌉\lceil |cs| / 2 \rceil members, drains the first half from hh, and drains the second half from wherever the first half left the main line. A single change, or an exhausted depth budget, falls back to seq\mathrm{seq}.

When the whole batch lands at once, the intermediate histories h⋅c1h \cdot c_1, h⋅c1c2,…h \cdot c_1 c_2, \ldots are never states of the main line. The main line jumps from hh to h⋅csh \cdot cs, and only that state was checked. This is the entire saving, and the gate property is stated so that it remains true.

/-! # 2. The merge queue: sequential admission and batching with bisection -/

namespace Queue

/-- Why a change was handed back. -/
inductive Reason where
  | conflict  -- it did not apply on the main line it met
  | red       -- tested alone on the main line it met, it failed the checks
  deriving DecidableEq

/-- The outcome of draining a batch. -/
structure Out (α : Type) where
  main    : List α                -- the main line afterwards
  commits : List (List α)         -- every state the main line moved to, in order
  ret     : List (α × Reason)     -- the changes handed back, with their reasons
  runs    : Nat                   -- how many times the checks were run

variable {α : Type}

/-- The reference: take one change at a time. `clean h c`: `c` applies on `h`; `g t`: `t` passes the checks. -/
def seq (g : List α → Bool) (clean : List α → α → Bool) : List α → List α → Out α
  | h, [] => ⟨h, [], [], 0⟩
  | h, c :: cs =>
    if clean h c then
      if g (h ++ [c]) then
        let o := seq g clean (h ++ [c]) cs
        ⟨o.main, (h ++ [c]) :: o.commits, o.ret, o.runs + 1⟩
      else
        let o := seq g clean h cs
        ⟨o.main, o.commits, (c, .red) :: o.ret, o.runs + 1⟩
    else
      let o := seq g clean h cs
      ⟨o.main, o.commits, (c, .conflict) :: o.ret, o.runs⟩

/-- Every change of the batch applies in turn. -/
def allClean (clean : List α → α → Bool) : List α → List α → Bool
  | _, [] => true
  | h, c :: cs => clean h c && allClean clean (h ++ [c]) cs

/-- Two halves drained one after the other. -/
def cat (n : Nat) (o1 o2 : Out α) : Out α :=
  ⟨o2.main, o1.commits ++ o2.commits, o1.ret ++ o2.ret, n + o1.runs + o2.runs⟩

/-- Batching with bisection: test the whole batch once; if it applies and passes, land it in one step;
otherwise split it in two halves and drain them in order. A singleton (or exhausted depth) falls back to `seq`. -/
def bis (g : List α → Bool) (clean : List α → α → Bool) : Nat → List α → List α → Out α
  | 0, h, cs => seq g clean h cs
  | _ + 1, h, [] => ⟨h, [], [], 0⟩
  | _ + 1, h, [c] => seq g clean h [c]
  | n + 1, h, a :: b :: r =>
    let cs := a :: b :: r
    let k := (cs.length + 1) / 2
    if allClean clean h cs then
      if g (h ++ cs) then ⟨h ++ cs, [h ++ cs], [], 1⟩
      else
        let o1 := bis g clean n h (cs.take k)
        cat 1 o1 (bis g clean n o1.main (cs.drop k))
    else
      let o1 := bis g clean n h (cs.take k)
      cat 0 o1 (bis g clean n o1.main (cs.drop k))

Safety and no loss

The following contract describes one drain. It is the same for both queues and holds for every check and every applicability test.

Contract of a drain from hh on batch cscs with outcome oo:

  1. Gate. Every state in o.commitso.\mathrm{commits} passes the checks, and o.maino.\mathrm{main} is either hh or one of those states.
  2. Append-only. o.main=h⋅Lo.\mathrm{main} = h \cdot L for some sub-sequence LL of cscs. Changes land in queue order, and the main line never loses one.
  3. No loss. LL together with the returned changes is a permutation of cscs. Nothing is dropped and nothing is duplicated.
  4. Reasons. A change returned as red failed the checks when tested alone on some main line, and a change returned as conflict was not clean on some main line.

Theorem 3 (safety and no loss). Sequential admission satisfies the contract. Bisection satisfies it at every depth, for every check gg and every applicability test. If the starting main line passes the checks, so does every state the main line holds during and after a drain.

Proof. For seq\mathrm{seq}, induct on the batch. Each branch adds one change to exactly one of LL or the returned list, and a new state is added to the commits only when the checks have just passed on it. For bis\mathrm{bis}, induct on the depth. The single-step landing satisfies the contract directly, with L=csL = cs. Otherwise the outcome is two drains joined end to end, and the contract is closed under that join: commits concatenate, the second drain starts where the first ended so the two LL concatenate, and the two permutations combine into a permutation of the two halves. Taking the first ⌈∣cs∣/2⌉\lceil |cs|/2 \rceil elements and dropping them recovers cscs. ∎

/-! ## Safety and no loss, for an arbitrary check `g` and applicability test `clean` -/

/-- The correctness contract of one drain from main line `h` on batch `cs`:
* (gate) every state the main line moves to passes the checks, and the final main line is one of them or `h`;
* (append-only) the main line only grows, by a sub-sequence `L` of the batch, in queue order;
* (no loss) the landed changes and the returned ones are exactly the batch, up to order;
* (reasons) a change returned as `red` failed the checks when tested alone on some main line,
  and one returned as `conflict` did not apply on some main line. -/
def Contract (g : List α → Bool) (clean : List α → α → Bool) (h cs : List α) (o : Out α) : Prop :=
  (∀ t ∈ o.commits, g t = true) ∧ (o.main = h ∨ o.main ∈ o.commits) ∧
  (∃ L, o.main = h ++ L ∧ L.Sublist cs ∧ (L ++ o.ret.map Prod.fst).Perm cs) ∧
  (∀ c, (c, Reason.red) ∈ o.ret → ∃ h', g (h' ++ [c]) = false) ∧
  (∀ c, (c, Reason.conflict) ∈ o.ret → ∃ h', clean h' c = false)

theorem perm_mix {A B C D X Y : List α} (h1 : (A ++ B).Perm X) (h2 : (C ++ D).Perm Y) :
    ((A ++ C) ++ (B ++ D)).Perm (X ++ Y) := by
  have e : ((A ++ C) ++ (B ++ D)).Perm ((A ++ B) ++ (C ++ D)) := by
    simp only [List.append_assoc]
    apply List.Perm.append_left A
    have := (List.perm_append_comm (l₁ := C) (l₂ := B)).append_right D
    simpa only [List.append_assoc] using this
  exact e.trans (h1.append h2)

theorem seq_contract (g : List α → Bool) (clean : List α → α → Bool) :
    ∀ (cs h : List α), Contract g clean h cs (seq g clean h cs) := by
  intro cs
  induction cs with
  | nil =>
    intro h
    refine ⟨by simp [seq], Or.inl rfl, ⟨[], by simp [seq], List.Sublist.slnil, by simp [seq]⟩,
      by simp [seq], by simp [seq]⟩
  | cons c cs ih =>
    intro h
    by_cases hc : clean h c = true
    · by_cases hg : g (h ++ [c]) = true
      · obtain ⟨g1, m1, ⟨L, e1, s1, p1⟩, r1, k1⟩ := ih (h ++ [c])
        simp only [seq, hc, hg, if_true]
        refine ⟨?_, ?_, ⟨c :: L, ?_, s1.cons₂ c, ?_⟩, r1, k1⟩
        · intro t ht
          rcases List.mem_cons.mp ht with rfl | ht
          · exact hg
          · exact g1 t ht
        · rcases m1 with m1 | m1
          · exact Or.inr (by rw [m1]; exact List.mem_cons_self ..)
          · exact Or.inr (List.mem_cons_of_mem _ m1)
        · simp [e1]
        · exact p1.cons c
      · have hg' : g (h ++ [c]) = false := by simpa using hg
        obtain ⟨g1, m1, ⟨L, e1, s1, p1⟩, r1, k1⟩ := ih h
        simp only [seq, hc, hg', if_true]
        refine ⟨g1, m1, ⟨L, e1, s1.cons c, ?_⟩, ?_, ?_⟩
        · exact (List.perm_middle).trans (p1.cons c)
        · intro c' hm
          rcases List.mem_cons.mp hm with he | hm
          · cases he; exact ⟨h, hg'⟩
          · exact r1 c' hm
        · intro c' hm
          rcases List.mem_cons.mp hm with he | hm
          · cases he
          · exact k1 c' hm
    · have hc' : clean h c = false := by simpa using hc
      obtain ⟨g1, m1, ⟨L, e1, s1, p1⟩, r1, k1⟩ := ih h
      simp only [seq, hc']
      refine ⟨g1, m1, ⟨L, e1, s1.cons c, ?_⟩, ?_, ?_⟩
      · exact (List.perm_middle).trans (p1.cons c)
      · intro c' hm
        rcases List.mem_cons.mp hm with he | hm
        · cases he
        · exact r1 c' hm
      · intro c' hm
        rcases List.mem_cons.mp hm with he | hm
        · cases he; exact ⟨h, hc'⟩
        · exact k1 c' hm

theorem cat_contract {g : List α → Bool} {clean : List α → α → Bool} {h xs ys : List α} {o1 o2 : Out α}
    (n : Nat) (c1 : Contract g clean h xs o1) (c2 : Contract g clean o1.main ys o2) :
    Contract g clean h (xs ++ ys) (cat n o1 o2) := by
  obtain ⟨g1, m1, ⟨L1, e1, s1, p1⟩, r1, k1⟩ := c1
  obtain ⟨g2, m2, ⟨L2, e2, s2, p2⟩, r2, k2⟩ := c2
  refine ⟨?_, ?_, ⟨L1 ++ L2, ?_, s1.append s2, ?_⟩, ?_, ?_⟩
  · intro t ht
    rcases List.mem_append.mp ht with ht | ht
    · exact g1 t ht
    · exact g2 t ht
  · show o2.main = h ∨ o2.main ∈ o1.commits ++ o2.commits
    rcases m2 with m2 | m2
    · rcases m1 with m1 | m1
      · exact Or.inl (m2.trans m1)
      · exact Or.inr (List.mem_append_left _ (m2 ▸ m1))
    · exact Or.inr (List.mem_append_right _ m2)
  · show o2.main = h ++ (L1 ++ L2)
    rw [e2, e1, List.append_assoc]
  · show (L1 ++ L2 ++ (o1.ret ++ o2.ret).map Prod.fst).Perm (xs ++ ys)
    rw [List.map_append]
    exact perm_mix p1 p2
  · intro c hc
    rcases List.mem_append.mp hc with hc | hc
    · exact r1 c hc
    · exact r2 c hc
  · intro c hc
    rcases List.mem_append.mp hc with hc | hc
    · exact k1 c hc
    · exact k2 c hc

/-- SAFETY AND NO LOSS for batching with bisection, at every depth, for every check and applicability test. -/
theorem bis_contract (g : List α → Bool) (clean : List α → α → Bool) :
    ∀ (n : Nat) (h cs : List α), Contract g clean h cs (bis g clean n h cs) := by
  intro n
  induction n with
  | zero => intro h cs; exact seq_contract g clean cs h
  | succ n ih =>
    intro h cs
    match cs with
    | [] => exact seq_contract g clean [] h
    | [c] => exact seq_contract g clean [c] h
    | a :: b :: r =>
      have split : ∀ m, Contract g clean h (a :: b :: r)
          (cat m (bis g clean n h ((a :: b :: r).take (((a :: b :: r).length + 1) / 2)))
            (bis g clean n (bis g clean n h ((a :: b :: r).take (((a :: b :: r).length + 1) / 2))).main
              ((a :: b :: r).drop (((a :: b :: r).length + 1) / 2)))) := by
        intro m
        have := cat_contract m (ih h ((a :: b :: r).take (((a :: b :: r).length + 1) / 2))) (ih _ ((a :: b :: r).drop (((a :: b :: r).length + 1) / 2)))
        rwa [List.take_append_drop] at this
      simp only [bis]
      by_cases hc : allClean clean h (a :: b :: r) = true
      · by_cases hg : g (h ++ a :: b :: r) = true
        · simp only [hc, hg, if_true]
          refine ⟨?_, Or.inr (List.mem_singleton_self _), ⟨a :: b :: r, rfl, List.Sublist.refl _, by simp⟩,
            by simp, by simp⟩
          intro t ht
          rw [List.mem_singleton.mp ht]; exact hg
        · simp only [hc, hg, if_true]
          exact split 1
      · simp only [hc]
        exact split 0

/-- Every state the main line ever holds passed the checks (given that the starting state did). -/
theorem bis_main_gated (g : List α → Bool) (clean : List α → α → Bool) (n : Nat) (h cs : List α)
    (h0 : g h = true) : g (bis g clean n h cs).main = true ∧ ∀ t ∈ (bis g clean n h cs).commits, g t = true := by
  obtain ⟨g1, m1, _⟩ := bis_contract g clean n h cs
  refine ⟨?_, g1⟩
  rcases m1 with m1 | m1
  · rw [m1]; exact h0
  · exact g1 _ m1

end Queue

Refinement and cost

Bisection is safe, but is it the same queue as one-at-a-time admission? In general it is not, and the reason is worth seeing. Suppose change 1 alone breaks the build and change 2 fixes it. The pair passes the checks. Bisection lands both in one step, while sequential admission returns 1 as red and then lands 2 alone. Both outcomes are safe, but they differ (the concrete checks below verify this example). The checks are not a function of the individual changes.

Refinement holds once the checks are such a function. In the separable fault model, each change is either faulty or not, and a state passes exactly when it contains no faulty change. Nothing conflicts. This is the setting of group testing, and it is a reasonable model of independent breakages.

Theorem 4 (refinement). In the separable fault model, starting from a passing main line, bisection at every depth ends on the same main line as sequential admission, namely hh followed by the non-faulty changes in queue order. It also returns the same list: the faulty changes in queue order, each marked red.

Proof. Compute both in closed form. For seq\mathrm{seq}, induct on the batch: a good change passes on a passing main line, and a faulty one fails on it. For bis\mathrm{bis}, induct on the depth. If the whole batch passes, it contains no faulty change, so the closed form keeps all of it. Otherwise the two halves are drained in order, and filtering commutes with concatenation. The main line after the first half still contains no faulty change, so the hypothesis carries over to the second half. ∎

Theorem 5 (cost). In the separable fault model, starting from a passing main line, with kk faulty changes in a batch of at most 2d2^d and depth budget at least dd, bisection runs the checks at most

1+2kd1 + 2kd

times. Sequential admission runs them once per change.

Proof. Induct on the depth. A batch with no faulty change passes at the first run. Otherwise k≥1k \ge 1, and the cost is one run plus the cost of the two halves, each of at most 2d−12^{d-1} changes and containing k1+k2=kk_1 + k_2 = k faulty ones. By induction this is at most

1+(1+2k1(d−1))+(1+2k2(d−1))=3+2k(d−1)≤1+2kd,1 + (1 + 2k_1(d-1)) + (1 + 2k_2(d-1)) = 3 + 2k(d-1) \le 1 + 2kd,

where the last step uses k≥1k \ge 1. ∎

For one faulty change in 64, the bound is 1+2⋅1⋅6=131 + 2 \cdot 1 \cdot 6 = 13, and the queue uses exactly 13 runs, against 64 for sequential admission. A clean batch of 64 costs one run. With 8 changes of which 2 are faulty, the bound is 13 and bisection uses 11. The bound is the standard cost of recursive halving, and it is good when faults are rare: kk faults among NN changes cost O(klog⁡N)O(k \log N) runs instead of NN.

The last theorem in this group is progress, and it holds for every check.

Theorem 6 (each drain consumes its batch). For every check and applicability test, every change in the batch either appears in the part of the main line added by the drain or is returned with a reason.

Proof. This is the permutation clause of the contract, read one element at a time. ∎

/-! ## Refinement and cost, when failures are caused by individual faulty changes -/

namespace Queue

variable {α : Type}

/-- The separable fault model: some changes are faulty (`B c`), and a state passes the checks exactly when it
contains no faulty change. -/
def sep (B : α → Bool) (t : List α) : Bool := t.all (fun c => !B c)

/-- No change ever conflicts. -/
def always : List α → α → Bool := fun _ _ => true

theorem sep_append (B : α → Bool) (x y : List α) : sep B (x ++ y) = (sep B x && sep B y) := by
  simp [sep, List.all_append]

theorem allClean_always : ∀ (h cs : List α), allClean always h cs = true
  | _, [] => rfl
  | h, _ :: cs => by simp [allClean, always, allClean_always (h ++ _) cs]

theorem sep_filter_good {B : α → Bool} {l : List α} (h : sep B l = true) : l.filter (fun c => !B c) = l := by
  rw [List.filter_eq_self]; simpa [sep, List.all_eq_true] using h

theorem sep_filter_bad {B : α → Bool} {l : List α} (h : sep B l = true) : l.filter B = [] := by
  rw [List.filter_eq_nil_iff]; simpa [sep, List.all_eq_true] using h

theorem sep_of_no_bad {B : α → Bool} {l : List α} (h : (l.filter B).length = 0) : sep B l = true := by
  have h' : l.filter B = [] := List.eq_nil_of_length_eq_zero h
  rw [List.filter_eq_nil_iff] at h'
  simpa [sep, List.all_eq_true] using h'

/-- The reference queue in the separable model, in closed form: it keeps exactly the good changes, in order. -/
theorem seq_sep (B : α → Bool) : ∀ (cs h : List α), sep B h = true →
    (seq (sep B) always h cs).main = h ++ cs.filter (fun c => !B c) ∧
    (seq (sep B) always h cs).ret = (cs.filter B).map (fun c => (c, Reason.red)) ∧
    (seq (sep B) always h cs).runs = cs.length := by
  intro cs
  induction cs with
  | nil => intro h _; simp [seq]
  | cons c cs ih =>
    intro h hh
    cases hc : B c
    · have hg : sep B (h ++ [c]) = true := by rw [sep_append, hh]; simp [sep, hc]
      obtain ⟨e1, e2, e3⟩ := ih (h ++ [c]) hg
      simp [seq, always, hg, e1, e2, e3, hc]
    · have hg : sep B (h ++ [c]) = false := by simp [sep_append, hh, sep, hc]
      obtain ⟨e1, e2, e3⟩ := ih h hh
      simp [seq, always, hg, e1, e2, e3, hc]

/-- Bisection in closed form in the separable model: the same good changes land, the same faulty ones return. -/
theorem bis_sep (B : α → Bool) : ∀ (n : Nat) (h cs : List α), sep B h = true →
    (bis (sep B) always n h cs).main = h ++ cs.filter (fun c => !B c) ∧
    (bis (sep B) always n h cs).ret = (cs.filter B).map (fun c => (c, Reason.red)) := by
  intro n
  induction n with
  | zero => intro h cs hh; exact ⟨(seq_sep B cs h hh).1, (seq_sep B cs h hh).2.1⟩
  | succ n ih =>
    intro h cs hh
    match cs with
    | [] => simp [bis]
    | [c] => exact ⟨(seq_sep B [c] h hh).1, (seq_sep B [c] h hh).2.1⟩
    | a :: b :: r =>
      simp only [bis, allClean_always, if_true]
      by_cases hg : sep B (h ++ a :: b :: r) = true
      · have hcs : sep B (a :: b :: r) = true := by
          rw [sep_append, hh, Bool.true_and] at hg; exact hg
        simp only [hg, if_true]
        exact ⟨by rw [sep_filter_good hcs], by rw [sep_filter_bad hcs]; rfl⟩
      · simp only [hg]
        generalize ((a :: b :: r).length + 1) / 2 = k
        obtain ⟨e1, r1⟩ := ih h ((a :: b :: r).take k) hh
        have hh1 : sep B (bis (sep B) always n h ((a :: b :: r).take k)).main = true := by
          rw [e1, sep_append, hh, Bool.true_and]
          simp [sep, List.all_eq_true]
        obtain ⟨e2, r2⟩ := ih _ ((a :: b :: r).drop k) hh1
        refine ⟨?_, ?_⟩
        · show (bis (sep B) always n _ _).main = _
          rw [e2, e1, List.append_assoc, ← List.filter_append, List.take_append_drop]
        · show (bis (sep B) always n h _).ret ++ (bis (sep B) always n _ _).ret = _
          rw [r1, r2, ← List.map_append, ← List.filter_append, List.take_append_drop]

/-- REFINEMENT: in the separable model, batching with bisection ends exactly where one-at-a-time admission ends,
and hands back exactly the same changes, in the same order, for the same reason. -/
theorem bis_refines_seq (B : α → Bool) (n : Nat) (h cs : List α) (hh : sep B h = true) :
    (bis (sep B) always n h cs).main = (seq (sep B) always h cs).main ∧
    (bis (sep B) always n h cs).ret = (seq (sep B) always h cs).ret := by
  rw [(bis_sep B n h cs hh).1, (bis_sep B n h cs hh).2, (seq_sep B cs h hh).1, (seq_sep B cs h hh).2.1]
  exact ⟨rfl, rfl⟩

/-- COST: with `k` faulty changes in a batch of at most `2 ^ d` and depth `n ≥ d`,
bisection runs the checks at most `1 + 2·k·d` times (one-at-a-time admission runs them once per change). -/
theorem bis_runs (B : α → Bool) : ∀ (n : Nat) (h cs : List α) (d : Nat), sep B h = true →
    cs.length ≤ 2 ^ d → d ≤ n →
    (bis (sep B) always n h cs).runs ≤ 1 + 2 * ((cs.filter B).length * d) := by
  intro n
  induction n with
  | zero =>
    intro h cs d hh hl hd
    have : d = 0 := by omega
    subst this
    rw [show bis (sep B) always 0 h cs = seq (sep B) always h cs from rfl, (seq_sep B cs h hh).2.2]
    have : cs.length ≤ 1 := by simpa using hl
    omega
  | succ n ih =>
    intro h cs d hh hl hd
    match cs with
    | [] => simp [bis]
    | [c] =>
      rw [show bis (sep B) always (n + 1) h [c] = seq (sep B) always h [c] from rfl, (seq_sep B [c] h hh).2.2]
      simp
    | a :: b :: r =>
      simp only [bis, allClean_always, if_true]
      by_cases hg : sep B (h ++ a :: b :: r) = true
      · simp only [hg, if_true]; omega
      · simp only [hg]
        have hcs : ¬ sep B (a :: b :: r) = true := by
          rw [sep_append, hh, Bool.true_and] at hg; exact hg
        have hk : 0 < ((a :: b :: r).filter B).length := by
          rcases Nat.eq_zero_or_pos ((a :: b :: r).filter B).length with e | e
          · exact absurd (sep_of_no_bad e) hcs
          · exact e
        obtain ⟨d', rfl⟩ : ∃ d', d = d' + 1 := by
          cases d with
          | zero => simp at hl
          | succ d' => exact ⟨d', rfl⟩
        have hp : 2 ^ (d' + 1) = 2 * 2 ^ d' := by rw [Nat.pow_succ, Nat.mul_comm]
        have hlen : (a :: b :: r).length ≤ 2 * 2 ^ d' := hp ▸ hl
        generalize hL : (a :: b :: r) = cs at *
        generalize hK : (cs.length + 1) / 2 = k
        have ht : (cs.take k).length ≤ 2 ^ d' := by rw [List.length_take]; omega
        have hd' : (cs.drop k).length ≤ 2 ^ d' := by rw [List.length_drop]; omega
        have i1 := ih h (cs.take k) d' hh ht (by omega)
        have hh1 : sep B (bis (sep B) always n h (cs.take k)).main = true := by
          rw [(bis_sep B n h (cs.take k) hh).1, sep_append, hh, Bool.true_and]
          simp [sep, List.all_eq_true]
        have i2 := ih _ (cs.drop k) d' hh1 hd' (by omega)
        have hsplit : (cs.filter B).length = ((cs.take k).filter B).length + ((cs.drop k).filter B).length := by
          rw [← List.length_append, ← List.filter_append, List.take_append_drop]
        show 1 + (bis (sep B) always n h (cs.take k)).runs + (bis (sep B) always n _ (cs.drop k)).runs ≤ _
        generalize ((cs.take k).filter B).length = k1 at *
        generalize ((cs.drop k).filter B).length = k2 at *
        rw [hsplit] at hk ⊢
        have m1 : (k1 + k2) * (d' + 1) = k1 * d' + k2 * d' + (k1 + k2) := by
          rw [Nat.mul_succ, Nat.add_mul]
        rw [m1]
        omega

/-- DRAIN: one round consumes the whole batch: every change either lands or comes back with a reason. -/
theorem bis_drains (g : List α → Bool) (clean : List α → α → Bool) (n : Nat) (h cs : List α) :
    ∀ c ∈ cs, (∃ L, (bis g clean n h cs).main = h ++ L ∧ c ∈ L) ∨ ∃ r, (c, r) ∈ (bis g clean n h cs).ret := by
  intro c hc
  obtain ⟨_, _, ⟨L, e, _, p⟩, _, _⟩ := bis_contract g clean n h cs
  have := p.symm.subset hc
  rcases List.mem_append.mp this with hl | hr
  · exact Or.inl ⟨L, e, hl⟩
  · obtain ⟨⟨c', r⟩, hm, he⟩ := List.mem_map.mp hr
    exact Or.inr ⟨r, by cases he; exact hm⟩

end Queue

Footprints inside the queue

The queue above is generic in its applicability test. Footprints supply one: replay the history from an initial state s0s_0, and ask whether the change is ready on the result. Changes are now footprints, and histories are lists of them.

Footprint applicability. fpCleans0(h,c)\mathrm{fpClean}_{s_0}(h, c) holds when landing hh from s0s_0 succeeds with some state ss and cc is ready on ss.

The useful fact is that landing earlier members of a disjoint batch never makes a later member stale.

Theorem 7 (disjoint batches). Let the main line hh replay to state ss, and let the batch cscs be pairwise disjoint with every member ready on ss.

  1. Every member applies in turn: the batch is clean under fpCleans0\mathrm{fpClean}_{s_0}.
  2. If the checks pass on h⋅csh \cdot cs, bisection with any depth budget of at least 1 lands the whole batch, returns nothing, and runs the checks at most once.
  3. Every permutation of cscs replays to the same state from hh, so the state the main line replays to does not depend on the order in which the queue received the batch.

Proof. (1) Induct on the batch. The first member is ready on ss. Landing it gives put(c,s)\mathrm{put}(c, s), and by Theorem 1 each later member is still ready there. (2) With (1), the first test of bis\mathrm{bis} succeeds, and so does the check. (3) Replaying h⋅csh \cdot cs is replaying hh and then cscs, and Theorem 2 applies to the second part. ∎

The hypothesis “ready on ss” is what an agent establishes when it reads the current main line before working. If another agent’s disjoint change lands first, the hypothesis survives, by Theorem 1. If an overlapping change lands first, the agent’s change returns as conflict, which is the intended outcome: its expectations are out of date.

/-! # 3. Footprints inside the queue -/

namespace Compose
open Footprint Queue

variable {K V : Type} [DecidableEq K] [DecidableEq V]

/-- The applicability test that footprints induce: replay the main line from `s0`, then compare-and-swap. -/
def fpClean (s0 : K → V) (h : List (Fp K V)) (c : Fp K V) : Bool :=
  match landAll s0 h with
  | some s => decide (Ready c s)
  | none => false

theorem landAll_append : ∀ (s : K → V) (l1 l2 : List (Fp K V)),
    landAll s (l1 ++ l2) = (landAll s l1).bind (fun t => landAll t l2)
  | s, [], l2 => by simp [landAll]
  | s, f :: l1, l2 => by
    simp only [List.cons_append, landAll]
    cases land s f <;> simp [landAll_append _ l1 l2]

/-- A batch whose footprints are pairwise disjoint, each applicable on the current main line,
applies in full: landing earlier members never makes a later one stale. -/
theorem disjoint_allClean (s0 : K → V) : ∀ (cs h : List (Fp K V)) (s : K → V),
    landAll s0 h = some s → cs.Pairwise Disj → (∀ c ∈ cs, Ready c s) →
    allClean (fpClean s0) h cs = true := by
  intro cs
  induction cs with
  | nil => intro _ _ _ _ _; rfl
  | cons c cs ih =>
    intro h s hs hp hr
    have hc : Ready c s := hr c (List.mem_cons_self ..)
    have hs' : landAll s0 (h ++ [c]) = some (put c s) := by
      rw [landAll_append, hs]; simp [landAll, land, hc]
    have hr' : ∀ c' ∈ cs, Ready c' (put c s) := fun c' hc' =>
      (ready_put_disj ((List.pairwise_cons.mp hp).1 c' hc') s).mpr (hr c' (List.mem_cons_of_mem _ hc'))
    have h1 : fpClean s0 h c = true := by simp [fpClean, hs, hc]
    simp only [allClean, h1, Bool.true_and]
    exact ih (h ++ [c]) (put c s) hs' (List.pairwise_cons.mp hp).2 hr'

/-- DISJOINT WORK NEVER CONFLICTS IN THE QUEUE: such a batch, if the checks pass on the whole of it,
lands in full, with nothing returned, in at most one run of the checks. -/
theorem disjoint_lands (g : List (Fp K V) → Bool) (s0 : K → V) (n : Nat) (h cs : List (Fp K V)) (s : K → V)
    (hs : landAll s0 h = some s) (hp : cs.Pairwise Disj) (hr : ∀ c ∈ cs, Ready c s)
    (hg : g (h ++ cs) = true) :
    (bis g (fpClean s0) (n + 1) h cs).main = h ++ cs ∧ (bis g (fpClean s0) (n + 1) h cs).ret = [] ∧
    (bis g (fpClean s0) (n + 1) h cs).runs ≤ 1 := by
  have ha := disjoint_allClean s0 cs h s hs hp hr
  match cs, ha, hg with
  | [], _, _ => simp [bis]
  | [c], ha, hg =>
    have h1 : fpClean s0 h c = true := by simpa [allClean] using ha
    simp [bis, seq, h1, hg]
  | a :: b :: r, ha, hg => simp [bis, ha, hg]

/-- Order does not matter: two queue orders of a pairwise-disjoint batch reach the same state. -/
theorem queue_order_free (s0 : K → V) (h : List (Fp K V)) {cs cs' : List (Fp K V)} (p : cs.Perm cs')
    (hp : cs.Pairwise Disj) : landAll s0 (h ++ cs) = landAll s0 (h ++ cs') := by
  rw [landAll_append, landAll_append]
  cases landAll s0 h with
  | none => rfl
  | some t => exact landAll_perm p hp t

end Compose

Leases

Leases are granted by a single arbiter that serves requests in arrival order. A request names an agent and a time. The claim state is either empty or a holder with an expiry time.

Grant rule. A request from agent aa at time tt is granted when the claim is empty, when aa is the current holder (a renewal), or when the current lease has expired, i.e. its expiry is at most tt. A grant sets the holder to aa and the expiry to t+Tt + T. Requests whose times are nondecreasing are called monotone.

Theorem 8 (mutual exclusion). For monotone requests, if a grant to agent aa at time t1t_1 is followed, anywhere later in the run, by a grant to a different agent at time t2t_2, then t1+T≤t2t_1 + T \le t_2. Consequently the lease windows [t1,t1+T)[t_1, t_1 + T) and [t2,t2+T)[t_2, t_2 + T) of two grants to different agents never share a time.

Proof. First show that while aa holds the claim with expiry ee, no other agent is granted it before ee. Induct on the remaining requests. A renewal by aa moves the expiry to t+T≥et + T \ge e and keeps the same holder. A grant to another agent happens only at a time of at least the expiry. A refused request changes nothing, and monotonicity carries the time bound forward. Exclusion then follows for every pair of grants: each grant starts such a holding period with expiry t1+Tt_1 + T. ∎

Because the statement covers every pair of grants, renewals are covered too. After the last renewal by aa at time tt, the next grant to another agent is at time at least t+Tt + T.

/-! # 4. Leases: time-bounded exclusive claims -/

namespace Lease

/-- A request: `agent` asks for the claim at time `time`. -/
structure Req where
  agent : Nat
  time  : Nat

/-- The claim: who holds it and until when (exclusive), if anyone ever took it. -/
abbrev St := Option (Nat × Nat)

/-- Granted when nobody holds the claim, when the holder's lease has run out, or as a renewal by the holder. -/
def grantable (s : St) (r : Req) : Bool :=
  match s with
  | none => true
  | some (a, e) => decide (r.agent = a) || decide (e ≤ r.time)

/-- Serve requests in order with lease length `T`; return the grants, in order. -/
def run (T : Nat) : St → List Req → List Req
  | _, [] => []
  | s, r :: rs => if grantable s r then r :: run T (some (r.agent, r.time + T)) rs else run T s rs

/-- Requests arrive in nondecreasing time. -/
def Mono (rs : List Req) : Prop := rs.Pairwise (fun r1 r2 => r1.time ≤ r2.time)

theorem run_sub (T : Nat) : ∀ (rs : List Req) (s : St) (g : Req), g ∈ run T s rs → g ∈ rs
  | [], _, _, h => by simp [run] at h
  | r :: rs, s, g, h => by
    unfold run at h
    split at h
    · rcases List.mem_cons.mp h with e | h
      · exact e ▸ List.mem_cons_self ..
      · exact List.mem_cons_of_mem _ (run_sub T rs _ g h)
    · exact List.mem_cons_of_mem _ (run_sub T rs _ g h)

/-- Once `a` holds the claim until `e`, nobody else is granted it before `e`. -/
theorem no_steal (T : Nat) : ∀ (rs : List Req) (a e t0 : Nat), Mono rs → (∀ r ∈ rs, t0 ≤ r.time) →
    e ≤ t0 + T → ∀ g ∈ run T (some (a, e)) rs, g.agent ≠ a → e ≤ g.time := by
  intro rs
  induction rs with
  | nil => intro _ _ _ _ _ _ g hg; simp [run] at hg
  | cons r rs ih =>
    intro a e t0 hm ht he g hg hne
    have hm' : Mono rs := (List.pairwise_cons.mp hm).2
    have hr : ∀ r' ∈ rs, r.time ≤ r'.time := (List.pairwise_cons.mp hm).1
    have ht0 : t0 ≤ r.time := ht r (List.mem_cons_self ..)
    unfold run at hg
    by_cases hgr : grantable (some (a, e)) r = true
    · rw [if_pos hgr] at hg
      simp only [grantable, Bool.or_eq_true, decide_eq_true_eq] at hgr
      rcases List.mem_cons.mp hg with rfl | hg
      · rcases hgr with h1 | h1
        · exact absurd h1 hne
        · exact h1
      · rcases hgr with h1 | h1
        · -- renewal by the holder
          have := ih r.agent (r.time + T) r.time hm' hr (Nat.le_refl _) g hg (by rw [← h1] at hne; exact hne)
          omega
        · -- the claim had run out; everything later is no earlier than `r.time ≥ e`
          have := hr g (run_sub T rs _ g hg)
          omega
    · rw [if_neg hgr] at hg
      exact ih a e r.time hm' hr (by omega) g hg hne

/-- MUTUAL EXCLUSION: whenever a grant to one agent is followed by a grant to another, the second comes no
earlier than the end of the first lease. So the lease windows `[t, t + T)` of different agents never overlap. -/
theorem exclusive (T : Nat) : ∀ (rs : List Req) (s : St), Mono rs →
    (run T s rs).Pairwise (fun g1 g2 => g1.agent ≠ g2.agent → g1.time + T ≤ g2.time) := by
  intro rs
  induction rs with
  | nil => intro s _; simp [run]
  | cons r rs ih =>
    intro s hm
    have hm' : Mono rs := (List.pairwise_cons.mp hm).2
    have hr : ∀ r' ∈ rs, r.time ≤ r'.time := (List.pairwise_cons.mp hm).1
    unfold run
    split
    · refine List.pairwise_cons.mpr ⟨?_, ih _ hm'⟩
      intro g hg hne
      exact no_steal T rs r.agent (r.time + T) r.time hm' hr (Nat.le_refl _) g hg (fun e => hne e.symm)
    · exact ih s hm'

/-- The windows of two different holders are disjoint. -/
theorem windows_disjoint (T : Nat) (rs : List Req) (hm : Mono rs) {g1 g2 : Req}
    (h12 : [g1, g2].Sublist (run T none rs)) (hne : g1.agent ≠ g2.agent) (t : Nat) :
    ¬ (g1.time ≤ t ∧ t < g1.time + T ∧ g2.time ≤ t ∧ t < g2.time + T) := by
  have hp := (exclusive T rs none hm).sublist h12
  have := (List.pairwise_cons.mp hp).1 g2 (List.mem_singleton_self _) hne
  omega

end Lease

Groupings and prerequisites

A task has an identifier, a duration and a list of prerequisite tasks. A grouping places each task in a milestone and each milestone in a plan, and lets milestones and plans declare prerequisite milestones and plans.

Waits. Task jj waits for task dd when dd is a prerequisite of jj, when dd‘s milestone is a prerequisite of jj‘s milestone, or when dd‘s plan is a prerequisite of jj‘s plan. This is the induced relation on tasks.

Combined graph. Its nodes are tasks, milestones and plans. Its edges run from a task to its prerequisite tasks, to the milestones and plans its own milestone and plan wait for, from a milestone to the tasks it holds and to the milestones and plans it waits for (including those its plan waits for), and from a plan to the milestones it holds and to the plans it waits for.

Acyclicity of a relation means a rank into the natural numbers that strictly decreases along every edge. Held means that every milestone or plan that carries a declared prerequisite holds at least one task, and so does every milestone whose plan carries one.

A rank rules out every closed walk, and Lean proves this. For a finite graph the converse also holds: a graph with no cycle has a rank, for instance the length of the longest path out of each node. That converse is not proved here, so the rank is the definition of acyclicity in this article.

Theorem 9 (acyclicity characterisation). If the combined graph is acyclic, so is the induced relation on tasks. If Held holds, the converse is also true. Without Held the converse fails.

Proof. Combined to induced: each induced edge is a path in the combined graph, either a direct task edge, or task to milestone to task, or task to plan to milestone to task, so the combined rank decreases along it. Induced to combined: given a task rank rr, place each group just above its highest task. Let top(G)\mathrm{top}(G) be 1+max⁡r1 + \max r over the tasks of group GG, or 00 if it holds none, and set

R(task t)=3(r(t)+1),R(milestone m)=3 top(m)+1,R(plan p)=3 top(p)+2.R(\text{task } t) = 3(r(t) + 1), \quad R(\text{milestone } m) = 3\,\mathrm{top}(m) + 1, \quad R(\text{plan } p) = 3\,\mathrm{top}(p) + 2 .

Each kind of edge is checked separately. The edges that leave a group for another group use Held. The source group holds some task t0t_0, and every task of the target group is waited on by t0t_0, so the target’s top is at most r(t0)r(t_0), which is below the source’s top. For the failure without Held, take two milestones that hold no tasks and wait for each other. The induced relation is empty, hence acyclic, while the combined graph has a cycle. ∎

The practical reading is that a planner can check only the induced task relation, as long as it refuses prerequisites on empty groups.

/-! # 5. Task groupings with precedence -/

namespace Groups

/-- A task: an identifier, a duration, and the identifiers of the tasks it depends on. -/
structure Task where
  id   : Nat
  dur  : Nat
  deps : List Nat

/-- Each task sits in one milestone, each milestone in one plan; milestones and plans declare dependencies. -/
structure Grouping where
  ms    : Task → Nat
  mp    : Nat → Nat
  mdeps : Nat → List Nat
  pdeps : Nat → List Nat

def planOf (g : Grouping) (t : Task) : Nat := g.mp (g.ms t)

/-- The induced relation: `j` waits for `d` by a task dependency, a milestone dependency, or a plan dependency. -/
def Waits (g : Grouping) (j d : Task) : Prop :=
  d.id ∈ j.deps ∨ g.ms d ∈ g.mdeps (g.ms j) ∨ planOf g d ∈ g.pdeps (planOf g j)

/-- Acyclicity witnessed by a rank that falls along every edge. -/
def IndAcyc (js : List Task) (g : Grouping) : Prop :=
  ∃ r : Task → Nat, ∀ j ∈ js, ∀ d ∈ js, Waits g j d → r d < r j

inductive Node where
  | task (j : Task)
  | mile (m : Nat)
  | plan (p : Nat)

/-- The combined graph over tasks, milestones and plans (waiter → awaited). -/
inductive Edge (js : List Task) (g : Grouping) : Node → Node → Prop where
  | dep {j d : Task} (hj : j ∈ js) (hd : d ∈ js) (h : d.id ∈ j.deps) : Edge js g (.task j) (.task d)
  | waitMile {j : Task} {m : Nat} (hj : j ∈ js) (h : m ∈ g.mdeps (g.ms j)) : Edge js g (.task j) (.mile m)
  | waitPlan {j : Task} {q : Nat} (hj : j ∈ js) (h : q ∈ g.pdeps (planOf g j)) : Edge js g (.task j) (.plan q)
  | holds {m : Nat} {t : Task} (ht : t ∈ js) (h : g.ms t = m) : Edge js g (.mile m) (.task t)
  | mileDep {m m' : Nat} (h : m' ∈ g.mdeps m) : Edge js g (.mile m) (.mile m')
  | planHolds {p m : Nat} (h : g.mp m = p) : Edge js g (.plan p) (.mile m)
  | planDep {p q : Nat} (h : q ∈ g.pdeps p) : Edge js g (.plan p) (.plan q)
  | inherit {m q : Nat} (h : q ∈ g.pdeps (g.mp m)) : Edge js g (.mile m) (.plan q)

def CombAcyc (js : List Task) (g : Grouping) : Prop := ∃ R : Node → Nat, ∀ x y, Edge js g x y → R y < R x

/-- Every milestone or plan that carries a declared dependency holds at least one task. -/
def Held (js : List Task) (g : Grouping) : Prop :=
  (∀ m, (g.mdeps m ≠ [] ∨ g.pdeps (g.mp m) ≠ []) → ∃ t ∈ js, g.ms t = m) ∧
  (∀ p, g.pdeps p ≠ [] → ∃ t ∈ js, planOf g t = p)

/-- A rank rules out every closed walk. -/
theorem rank_acyclic {β : Type} {E : β → β → Prop} {R : β → Nat} (h : ∀ x y, E x y → R y < R x) (x : β) :
    ¬ Relation.TransGen E x x := by
  have key : ∀ {x y}, Relation.TransGen E x y → R y < R x := by
    intro x y p
    induction p with
    | single e => exact h _ _ e
    | tail _ e ih => exact Nat.lt_trans (h _ _ e) ih
  exact fun p => Nat.lt_irrefl _ (key p)

theorem comb_no_cycle {js : List Task} {g : Grouping} (h : CombAcyc js g) (x : Node) :
    ¬ Relation.TransGen (Edge js g) x x := by
  obtain ⟨R, hR⟩ := h; exact rank_acyclic hR x

theorem ind_no_cycle {js : List Task} {g : Grouping} (h : IndAcyc js g) (j : Task) :
    ¬ Relation.TransGen (fun a b => a ∈ js ∧ b ∈ js ∧ Waits g a b) j j := by
  obtain ⟨r, hr⟩ := h
  exact rank_acyclic (R := r) (fun x y e => hr x e.1 y e.2.1 e.2.2) j

/-- Combined acyclic ⇒ induced acyclic, with no hypothesis. -/
theorem ind_of_comb {js : List Task} {g : Grouping} (h : CombAcyc js g) : IndAcyc js g := by
  obtain ⟨R, hR⟩ := h
  refine ⟨fun t => R (.task t), ?_⟩
  intro j hj d hd hw
  rcases hw with e | e | e
  · exact hR _ _ (Edge.dep hj hd e)
  · have e1 := hR _ _ (Edge.waitMile (js := js) hj e)
    have e2 := hR _ _ (Edge.holds (js := js) (g := g) hd rfl)
    exact Nat.lt_trans e2 e1
  · have e1 := hR _ _ (Edge.waitPlan (js := js) hj e)
    have e2 := hR _ _ (Edge.planHolds (js := js) (g := g) (m := g.ms d) rfl)
    have e3 := hR _ _ (Edge.holds (js := js) (g := g) hd rfl)
    exact Nat.lt_trans e3 (Nat.lt_trans e2 e1)

/-! The converse builds a combined rank from a task rank: a group sits just above its highest task. -/

def maxOf : List Nat → Nat
  | [] => 0
  | x :: xs => max x (maxOf xs)

theorem le_maxOf : ∀ {l : List Nat} {x : Nat}, x ∈ l → x ≤ maxOf l
  | _ :: _, _, .head _ => Nat.le_max_left _ _
  | _ :: _, _, .tail _ h => Nat.le_trans (le_maxOf h) (Nat.le_max_right _ _)

theorem maxOf_le : ∀ {l : List Nat} {b : Nat}, (∀ x ∈ l, x ≤ b) → maxOf l ≤ b
  | [], _, _ => Nat.zero_le _
  | x :: _, _, h => Nat.max_le.mpr ⟨h x (List.mem_cons_self ..), maxOf_le (fun y hy => h y (List.mem_cons_of_mem _ hy))⟩

/-- Top of a group: `1 +` the highest rank of a task with `f t = k`, or `0` when it holds none. -/
def top (js : List Task) (r : Task → Nat) (f : Task → Nat) (k : Nat) : Nat :=
  maxOf ((js.filter (fun t => f t == k)).map (fun t => r t + 1))

theorem le_top {js : List Task} {r : Task → Nat} {f : Task → Nat} {t : Task} {k : Nat} (ht : t ∈ js)
    (hk : f t = k) : r t + 1 ≤ top js r f k :=
  le_maxOf (List.mem_map.mpr ⟨t, List.mem_filter.mpr ⟨ht, by simp [hk]⟩, rfl⟩)

theorem top_le {js : List Task} {r : Task → Nat} {f : Task → Nat} {k b : Nat}
    (h : ∀ t ∈ js, f t = k → r t + 1 ≤ b) : top js r f k ≤ b := by
  apply maxOf_le
  intro x hx
  obtain ⟨t, ht, rfl⟩ := List.mem_map.mp hx
  obtain ⟨h1, h2⟩ := List.mem_filter.mp ht
  exact h t h1 (by simpa using h2)

def lift (js : List Task) (g : Grouping) (r : Task → Nat) : Node → Nat
  | .task t => 3 * (r t + 1)
  | .mile m => 3 * top js r g.ms m + 1
  | .plan p => 3 * top js r (planOf g) p + 2

/-- Induced acyclic ⇒ combined acyclic, when every group that carries a dependency holds a task. -/
theorem comb_of_ind {js : List Task} {g : Grouping} (hh : Held js g) (h : IndAcyc js g) : CombAcyc js g := by
  obtain ⟨r, hr⟩ := h
  refine ⟨lift js g r, ?_⟩
  intro x y e
  cases e with
  | @dep j d hj hd e =>
    have := hr j hj d hd (Or.inl e)
    show 3 * (r d + 1) < 3 * (r j + 1); omega
  | @waitMile j m hj e =>
    have : top js r g.ms m ≤ r j := top_le (fun t ht hm => hr j hj t ht (Or.inr (Or.inl (hm ▸ e))))
    show 3 * top js r g.ms m + 1 < 3 * (r j + 1); omega
  | @waitPlan j q hj e =>
    have : top js r (planOf g) q ≤ r j := top_le (fun t ht hq => hr j hj t ht (Or.inr (Or.inr (hq ▸ e))))
    show 3 * top js r (planOf g) q + 2 < 3 * (r j + 1); omega
  | @holds m t ht e =>
    have : r t + 1 ≤ top js r g.ms m := le_top ht e
    show 3 * (r t + 1) < 3 * top js r g.ms m + 1; omega
  | @mileDep m m' e =>
    obtain ⟨t0, ht0, hm0⟩ := hh.1 m (Or.inl (List.ne_nil_of_mem e))
    have h1 : top js r g.ms m' ≤ r t0 :=
      top_le (fun t ht hm => hr t0 ht0 t ht (Or.inr (Or.inl (by rw [hm, hm0]; exact e))))
    have h2 : r t0 + 1 ≤ top js r g.ms m := le_top ht0 hm0
    show 3 * top js r g.ms m' + 1 < 3 * top js r g.ms m + 1; omega
  | @planHolds p m e =>
    have : top js r g.ms m ≤ top js r (planOf g) p :=
      top_le (fun t ht hm => le_top ht (show g.mp (g.ms t) = p by rw [hm]; exact e))
    show 3 * top js r g.ms m + 1 < 3 * top js r (planOf g) p + 2; omega
  | @planDep p q e =>
    obtain ⟨t0, ht0, hp0⟩ := hh.2 p (List.ne_nil_of_mem e)
    have h1 : top js r (planOf g) q ≤ r t0 :=
      top_le (fun t ht hq => hr t0 ht0 t ht (Or.inr (Or.inr (by rw [hq, hp0]; exact e))))
    have h2 : r t0 + 1 ≤ top js r (planOf g) p := le_top ht0 hp0
    show 3 * top js r (planOf g) q + 2 < 3 * top js r (planOf g) p + 2; omega
  | @inherit m q e =>
    obtain ⟨t0, ht0, hm0⟩ := hh.1 m (Or.inr (List.ne_nil_of_mem e))
    have h1 : top js r (planOf g) q ≤ r t0 := top_le (fun t ht hq => by
      have hp : planOf g t ∈ g.pdeps (planOf g t0) := by
        show planOf g t ∈ g.pdeps (g.mp (g.ms t0)); rw [hq, hm0]; exact e
      exact hr t0 ht0 t ht (Or.inr (Or.inr hp)))
    have h2 : r t0 + 1 ≤ top js r g.ms m := le_top ht0 hm0
    show 3 * top js r (planOf g) q + 2 < 3 * top js r g.ms m + 1; omega

/-- ACYCLICITY CHARACTERISATION: under `Held`, the induced task relation is acyclic iff the combined graph is. -/
theorem ind_iff_comb {js : List Task} {g : Grouping} (hh : Held js g) : IndAcyc js g ↔ CombAcyc js g :=
  ⟨comb_of_ind hh, ind_of_comb⟩

/-- `Held` cannot be dropped: two empty milestones that depend on each other. -/
def gap : Grouping := ⟨fun _ => 0, fun _ => 0, fun m => if m = 1 then [2] else if m = 2 then [1] else [], fun _ => []⟩

theorem gap_ind : IndAcyc [] gap := ⟨fun _ => 0, fun _ h => nomatch h⟩

theorem gap_not_comb : ¬ CombAcyc [] gap := by
  intro h
  apply comb_no_cycle h (.mile 1)
  exact .tail (.single (Edge.mileDep (m := 1) (m' := 2) (by simp [gap])))
    (Edge.mileDep (m := 2) (m' := 1) (by simp [gap]))

A schedule assigns each task identifier a start time. It respects the grouping when every task starts no earlier than the end of every task it waits for.

Theorem 10 (schedules).

  1. A schedule respects the grouping exactly when each task starts after its prerequisite tasks have ended and after every task of each milestone and plan it waits for has ended. This is the eligibility rule of the architecture.
  2. If every duration is positive and a respecting schedule exists, the induced relation is acyclic.
  3. If the induced relation is acyclic, identifiers name tasks uniquely, and every duration is at most DD, then a respecting schedule exists: start each task at its rank times DD.

Proof. (1) unfolds the three cases of waiting. (2) uses start times as the rank. With positive durations, waiting forces a strictly later start. (3) If jj waits for dd then r(d)+1≤r(j)r(d) + 1 \le r(j), so dd ends by r(d)D+D≤r(j)Dr(d) D + D \le r(j) D. Unique identifiers make the start time of an identifier well defined. ∎

/-! ## Schedules that respect precedence -/

/-- A schedule gives each task identifier a start time. -/
abbrev Sched := Nat → Nat

def fin (st : Sched) (j : Task) : Nat := st j.id + j.dur

/-- The schedule honours the induced relation: a task starts after everything it waits for has ended. -/
def PrecG (js : List Task) (g : Grouping) (st : Sched) : Prop :=
  ∀ j ∈ js, ∀ d ∈ js, Waits g j d → fin st d ≤ st j.id

/-- `j` may start at `t`: its task dependencies have ended, and its declared milestones and plans are complete. -/
def GroupReady (js : List Task) (g : Grouping) (st : Sched) (j : Task) (t : Nat) : Prop :=
  (∀ d ∈ js, d.id ∈ j.deps → fin st d ≤ t) ∧
  (∀ m ∈ g.mdeps (g.ms j), ∀ d ∈ js, g.ms d = m → fin st d ≤ t) ∧
  (∀ q ∈ g.pdeps (planOf g j), ∀ d ∈ js, planOf g d = q → fin st d ≤ t)

/-- Respecting precedence is exactly the per-task start rule. -/
theorem precG_iff {js : List Task} {g : Grouping} {st : Sched} :
    PrecG js g st ↔ ∀ j ∈ js, GroupReady js g st j (st j.id) := by
  constructor
  · intro h j hj
    exact ⟨fun d hd e => h j hj d hd (Or.inl e),
      fun m hm d hd hdm => h j hj d hd (Or.inr (Or.inl (hdm ▸ hm))),
      fun q hq d hd hdq => h j hj d hd (Or.inr (Or.inr (hdq ▸ hq)))⟩
  · intro h j hj d hd hw
    obtain ⟨h1, h2, h3⟩ := h j hj
    rcases hw with e | e | e
    · exact h1 d hd e
    · exact h2 _ e d hd rfl
    · exact h3 _ e d hd rfl

/-- A precedence-respecting schedule with positive durations exists only if the induced relation is acyclic. -/
theorem ind_of_sched {js : List Task} {g : Grouping} {st : Sched} (hd : ∀ j ∈ js, 0 < j.dur)
    (h : PrecG js g st) : IndAcyc js g := by
  refine ⟨fun t => st t.id, fun j hj d hdm hw => ?_⟩
  have h1 : st d.id + d.dur ≤ st j.id := h j hj d hdm hw
  have h2 := hd d hdm
  show st d.id < st j.id
  omega

/-- Conversely, when identifiers name tasks uniquely and durations are at most `D`, an acyclic induced relation
has a precedence-respecting schedule: start each task at its rank times `D`. -/
theorem sched_of_ind {js : List Task} {g : Grouping} (h : IndAcyc js g) (D : Nat) (hD : ∀ j ∈ js, j.dur ≤ D)
    (hid : ∀ a ∈ js, ∀ b ∈ js, a.id = b.id → a = b) :
    ∃ st : Sched, PrecG js g st := by
  obtain ⟨r, hr⟩ := h
  -- start time of identifier `i`: rank of the task in `js` carrying it, times `D`
  let rk : Nat → Nat := fun i => match js.find? (fun t => t.id == i) with
    | some t => r t
    | none => 0
  have hrk : ∀ t ∈ js, rk t.id = r t := by
    intro t ht
    show (match js.find? (fun x => x.id == t.id) with | some t => r t | none => 0) = r t
    cases hf : js.find? (fun x => x.id == t.id) with
    | none =>
      have := List.find?_eq_none.mp hf t ht
      simp at this
    | some u =>
      have hu := List.mem_of_find?_eq_some hf
      have he : u.id = t.id := by simpa using List.find?_some hf
      simp only
      rw [hid u hu t ht he]
  refine ⟨fun i => rk i * D, fun j hj d hd hw => ?_⟩
  have hlt := hr j hj d hd hw
  show rk d.id * D + d.dur ≤ rk j.id * D
  rw [hrk d hd, hrk j hj]
  have h1 : (r d + 1) * D ≤ r j * D := Nat.mul_le_mul_right D hlt
  have h2 := hD d hd
  rw [Nat.succ_mul] at h1
  omega

end Groups

Concrete checks

The examples below are evaluated by the kernel. They fix the numbers quoted above, and the last three show the case where bisection and sequential admission part ways.

/-! # 6. Concrete checks -/

namespace Checks
open Queue

/-- Eight changes, two of them faulty (3 and 6): bisection lands the other six, in order, and returns 3 and 6. -/
def bad (c : Nat) : Bool := c == 3 || c == 6

example : (bis (sep bad) always 3 [] [1, 2, 3, 4, 5, 6, 7, 8]).main = [1, 2, 4, 5, 7, 8] := by decide
example : (bis (sep bad) always 3 [] [1, 2, 3, 4, 5, 6, 7, 8]).ret = [(3, .red), (6, .red)] := by decide
example : (bis (sep bad) always 3 [] [1, 2, 3, 4, 5, 6, 7, 8]).runs = 11 := by decide

/-- One faulty change among 64: bisection needs 13 runs, which is the bound `1 + 2·1·6` exactly;
one-at-a-time admission needs 64. A clean batch of 64 needs one. -/
example : (bis (sep (· == 40)) always 6 [] (List.range 64)).runs = 13 := by decide
example : (seq (sep (· == 40)) always [] (List.range 64)).runs = 64 := by decide
example : (bis (sep (· == 100)) always 6 [] (List.range 64)).runs = 1 := by decide

/-- Outside the separable model the two queues can part ways, both safely: here `[1]` fails the checks
but `[1, 2]` passes. Bisection lands the pair; one-at-a-time admission returns 1 and lands 2. -/
def fixup (t : List Nat) : Bool := t != [1]

example : (bis fixup always 1 [] [1, 2]).main = [1, 2] := by decide
example : (seq fixup always [] [1, 2]).main = [2] := by decide
example : (seq fixup always [] [1, 2]).ret = [(1, .red)] := by decide

end Checks

What the combination achieves

Each item of the goal is now a theorem or a stated boundary.

GoalResultHypotheses
1. GateTheorem 3the starting main line passes
2. No loss, with evidenceTheorem 3none: every check, every applicability test, every depth
3. Disjoint work never conflictsTheorems 1, 2, 7footprints declare every key touched
4. Exclusive claimsTheorem 8one arbiter, monotone request times
5. Consistent plansTheorems 9, 10Held; unique identifiers; positive, bounded durations
6. Progress and costTheorems 5, 6cost: separable faults, batch at most 2d2^d

Bisection matches one-at-a-time admission exactly in the separable fault model (Theorem 4). Outside it, the two can part ways, but both satisfy the full contract.

Limits and assumptions

  • Honest footprints. In the model, a change can only write its declared keys, because put\mathrm{put} does nothing else. In a real system, declaring every key a change reads or writes is an obligation on the agent or its tooling. An undeclared read breaks Theorem 1 without any visible sign. Enforcing footprints at write time, by rejecting writes outside the declared keys, turns this into a property of the system.
  • Deterministic checks. The check is a function of the history. A flaky check, one that passes and fails on the same state, falls outside the model. The gate property still holds for the runs that passed, but the reasons and the cost bound do not.
  • Refinement needs separable faults. Theorem 4 and Theorem 5 use the separable fault model and no conflicts. For a general check, the contract holds but bisection may land a set of changes that sequential admission would not, as the concrete checks show. A combination of conflicts and refinement is not proved.
  • Weak reasons. The contract says a red change failed the checks on some main line, and a conflict change did not apply on some main line. In both queues that main line is the actual one at the time, but the contract records only that one exists.
  • One queue, one arbiter. Everything is proved for a single queue and a single lease arbiter that serves requests in nondecreasing time. Several queues sharing a main line, a replicated arbiter, and clock drift between the arbiter and the holders are not modelled. As in the original lease protocol, a holder must stop working when its lease runs out by the arbiter’s clock, which needs a bound on clock drift.
  • Progress is per drain. Each drain consumes its batch (Theorem 6), and each drain terminates. A change that is returned and resubmitted forever is not ruled out, and no fairness between agents is proved.
  • Acyclicity is a rank. Rank implies no closed walk. The converse, for finite graphs, is standard but not proved here.
  • No cryptography. Nothing here relies on a cryptographic property. Histories are lists of changes, compared by equality, and no hash stands in for them.

Prior work

Validation of a transaction’s read and write sets at commit, with no locks during execution, is the method of “On Optimistic Methods for Concurrency Control” (ACM Transactions on Database Systems, 1981). The condition that operations with disjoint read and write sets can run in either order with the same result goes back to “Analysis of Programs for Parallel Processing” (IEEE Transactions on Electronic Computers, 1966). Theorems 1 and 2 are that condition, stated for a compare-and-swap on a declared footprint.

Time-bounded exclusive claims that the holder renews, and that others take only after expiry, are the leases of “Leases: An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency” (SOSP 1989). Theorem 8 is their exclusion property for a single arbiter.

Testing a pool of items with one test and splitting it when it fails is group testing, from “The Detection of Defective Members of Large Populations” (Annals of Mathematical Statistics, 1943). Recursive halving is the binary splitting of “A Method for Detecting All Defective Members in a Population by Group Testing” (Journal of the American Statistical Association, 1972). Theorem 5 is the standard cost bound of adaptive recursive halving, a simpler relative of that binary splitting, stated for a queue whose positives are handed back and whose negatives land.

Scheduling tasks along an acyclic prerequisite relation is the subject of “Topological Sorting of Large Networks” (Communications of the ACM, 1962). Theorem 10 is the timed form of that result, with a rank in place of a topological order.

What this article adds is the combination of the four parts, a statement of the goal it serves, and a single Lean file that proves the combination meets that goal under assumptions stated explicitly.