sgl_sched_layout
DefinitionDefinition code
import Definitions.Def_sgl_prologue
/-!
# The scheduler's tape assignment
Ten tapes: three inputs, four the delegate works on, a clock, a counter, and a
guide. `stdLayout` had nine — the guide is the tenth, and it has to be its own
tape because it is consumed as the loop runs while every other role must
survive to the next round.
The prologue's seven-role index is the same tapes under different names: its
worker is the first working tape, which the normalising walk never moves.
-/
namespace SipserGacsLautemann
/-- The layout the scheduler runs on. -/
def schedLayout : RoundLayout 10 where
src := fun i => ⟨i.val, by omega⟩
dst := fun j => ⟨3 + j.val, by omega⟩
clk := ⟨7, by omega⟩
cnt := ⟨8, by omega⟩
/-- The guide. -/
def schedGuide : Fin 10 := ⟨9, by omega⟩
/-- The prologue's roles, on this layout: three inputs, clock, guide, counter,
and a working tape to stand in as the normalising walk's idle partner. -/
def schedIdx : Fin 7 → Fin 10
| 0 => ⟨0, by omega⟩
| 1 => ⟨1, by omega⟩
| 2 => ⟨2, by omega⟩
| 3 => ⟨7, by omega⟩
| 4 => ⟨9, by omega⟩
| 5 => ⟨8, by omega⟩
| 6 => ⟨3, by omega⟩
theorem schedIdx_injective : Function.Injective schedIdx := by
intro a b hab
fin_cases a <;> fin_cases b <;> simp_all [schedIdx] <;>
exact absurd (congrArg Fin.val hab) (by decide)
theorem schedLayout_wf : schedLayout.Wf := by
refine ⟨?_, ?_, ?_, ?_, ?_⟩
· intro a b hab
have := congrArg Fin.val hab
simp [schedLayout] at this
exact Fin.ext (by omega)
· intro j hc
have := congrArg Fin.val hc
simp [schedLayout] at this
omega
· intro j hc
have := congrArg Fin.val hc
simp [schedLayout] at this
omega
· intro i j hc
have := congrArg Fin.val hc
simp [schedLayout] at this
omega
· intro hc
have := congrArg Fin.val hc
simp [schedLayout] at this
theorem schedLayout_src_clk : ∀ i, schedLayout.src i ≠ schedLayout.clk := by
intro i hc
have := congrArg Fin.val hc
simp [schedLayout] at this
omega
theorem schedLayout_src_cnt : ∀ i, schedLayout.src i ≠ schedLayout.cnt := by
intro i hc
have := congrArg Fin.val hc
simp [schedLayout] at this
omega
theorem schedGuide_clk : schedGuide ≠ schedLayout.clk := by
intro hc
have := congrArg Fin.val hc
simp [schedGuide, schedLayout] at this
theorem schedGuide_cnt : schedGuide ≠ schedLayout.cnt := by
intro hc
have := congrArg Fin.val hc
simp [schedGuide, schedLayout] at this
theorem schedGuide_dst : ∀ j, schedGuide ≠ schedLayout.dst j := by
intro j hc
have := congrArg Fin.val hc
simp [schedGuide, schedLayout] at this
omega
theorem schedGuide_src : ∀ i, schedGuide ≠ schedLayout.src i := by
intro i hc
have := congrArg Fin.val hc
simp [schedGuide, schedLayout] at this
omega
end SipserGacsLautemann