uniform_kserver_det_alg_serves
A deterministic online algorithm A taking a request list to a configuration serves requests if for every list of earlier requests ρ and current request r, the configuration A (ρ ++ [r]) serves r (meaning A (ρ ++ [r]) i = r i for some coordinate i).
Statement
def uniform_kserver_det_alg_serves {k : ℕ} {M : Fin k → Type*} (A : List (∀ i, M i) → (∀ i, M i)) : Prop
- Defined in
- arXiv:2610.37192 Sec. 6
- Verified
- 30 Oct 2026
- Axioms
- none listed
- Built on 1
- uniform_kserver_servesFor a natural number k, a family of uniform metric spaces M indexed by Fin k, and configurations x, r in the product space over Fin k, x…
- Used by 3
- uniform_kserver_det_schedule_is_scheduleFor a natural number k, a family of types M indexed by Fin k, an algorithm A : List (∀ i, M i) → (∀ i, M i) satisfying…
- 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
Given a natural number $k$ and a family of types $M : \text{Fin } k \to \text{Type*}$, a deterministic algorithm $A : \text{List} (\forall i, M i) \to (\forall i, M i)$ satisfies uniform_kserver_det_alg_serves if for every list of configurations $\rho : \text{List} (\forall i, M i)$ and every configuration $r : \forall i, M i$, the configuration output by $A$ on the extended history $\rho ++ [r]$ serves $r$ according to uniform_kserver_serves.
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
/-- A deterministic online algorithm serves requests if it serves the latest request on every sequence. -/ def uniform_kserver_det_alg_serves {k : ℕ} {M : Fin k → Type*} (A : List (∀ i, M i) → (∀ i, M i)) : Prop := ∀ (ρ : List (∀ i, M i)) (r : ∀ i, M i), uniform_kserver_serves (A (ρ ++ [r])) r