uniform_kserver_det_cost
For a natural number k, a family of types M indexed by Fin k with decidable equality, an algorithm A : List (∀ i, M i) → (∀ i, M i), an initial configuration a : ∀ i, M i, and a request sequence ρ : List (∀ i, M i), uniform_kserver_det_cost A a ρ is the offline movement cost uniform_kserver_offline_cost a (uniform_kserver_det_schedule A ρ).
Statement
def uniform_kserver_det_cost {k : ℕ} {M : Fin k → Type*} [∀ i, DecidableEq (M i)] (A : List (∀ i, M i) → (∀ i, M i)) (a : ∀ i, M i) (ρ : List (∀ i, M i)) : ℕ
- Defined in
- arXiv:2610.37192 Sec. 6
- Verified
- 30 Oct 2026
- Axioms
- none listed
- Built on 2
- uniform_kserver_offline_costFor a natural number k, a family of spaces M indexed by Fin k with decidable equality, an initial configuration a, and a list of…
- uniform_kserver_det_scheduleGiven types α and β, a mapping A : List α → β, and an input list ρ : List α, uniform_kserver_det_schedule A ρ is the list of elements of β…
- Used by 2
- uniform_kserver_det_k_one_competitiveFor generalized 1-server on any family of uniform metric spaces M indexed by Fin 1 with decidable equality and any initial configuration a…
- uniform_kserver_det_competitiveFor a natural number k, a family of types M indexed by Fin k with decidable equality, an algorithm A : List (∀ i, M i) → (∀ i, M i), an…
Read back from the Lean
A definition of uniform_kserver_det_cost: given a number of servers k : ℕ, a family of types M : Fin k → Type* with decidable equality on each M i, a deterministic algorithm A : List (∀ i, M i) → (∀ i, M i), an initial configuration a : ∀ i, M i, and an input sequence ρ : List (∀ i, M i), it computes the total transition cost (as a natural number) incurred by running A starting from configuration a on ρ.
Specifically, A is evaluated on each non-empty prefix ρ.take (t + 1) for t ∈ {0, ..., ρ.length - 1} to produce a schedule of configurations. The total cost is the sum of the Hamming distances (the number of coordinates i : Fin k that differ) between consecutive configurations along the path, beginning from a to the first configuration A (ρ.take 1), and then between each successive pair in the schedule.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Total movement cost incurred by deterministic algorithm A on ρ starting from a. -/ def uniform_kserver_det_cost {k : ℕ} {M : Fin k → Type*} [∀ i, DecidableEq (M i)] (A : List (∀ i, M i) → (∀ i, M i)) (a : ∀ i, M i) (ρ : List (∀ i, M i)) : ℕ := uniform_kserver_offline_cost a (uniform_kserver_det_schedule A ρ)