uniform_kserver_det_competitive
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 real γ, uniform_kserver_det_competitive k A a γ holds if uniform_kserver_det_alg_serves A and there exists a real constant c such that for every request sequence ρ : List (∀ i, M i), the deterministic cost uniform_kserver_det_cost A a ρ is at most γ * (uniform_kserver_opt k a ρ : ℝ) + c.
Statement
def uniform_kserver_det_competitive (k : ℕ) {M : Fin k → Type*} [∀ i, DecidableEq (M i)] (A : List (∀ i, M i) → (∀ i, M i)) (a : ∀ i, M i) (γ : ℝ) : Prop
- Defined in
- arXiv:2610.37192 Sec. 6
- Verified
- 30 Oct 2026
- Axioms
- none listed
- Built on 3
- uniform_kserver_det_alg_servesA deterministic online algorithm A taking a request list to a configuration serves requests if for every list of earlier requests ρ and…
- uniform_kserver_det_costFor 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…
- uniform_kserver_optFor a natural number k, a family of spaces M indexed by Fin k with decidable equality, an initial configuration a, and a list of requests…
- Used by 1
- 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…
Read back from the Lean
The declaration uniform_kserver_det_competitive asserts that a deterministic online algorithm A is γ-competitive for a uniform k-server problem with initial configuration a.
Specifically, given:
- k : ℕ (the number of servers/coordinates),
- a family of types M : Fin k → Type* with decidable equality on each M i,
- an algorithm A : List (∀ i, M i) → (∀ i, M i) mapping request sequences to configurations,
- an initial configuration a : ∀ i, M i,
- a competitive ratio γ : ℝ,
the definition states that:
1. A is a valid serving algorithm (uniform_kserver_det_alg_serves A): for every request sequence ρ and every next request r : ∀ i, M i, the configuration chosen by A on ρ ++ [r] agrees with r at some coordinate i : Fin k (i.e., ∃ i : Fin k, (A (ρ ++ [r])) i = r i).
2. There exists a real constant c : ℝ such that for every request sequence ρ : List (∀ i, M i), the total transition cost incurred by A (starting from a and moving to A (ρ.take (t + 1)) at each step t, where transition cost between two configurations is the number of coordinates where they differ) is at most γ times the optimal offline cost (uniform_kserver_opt k a ρ, the minimum total transition cost from a among all valid schedules of the same length whose configurations each match the corresponding request at some coordinate i), plus c.
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
/-- Competitiveness of a deterministic online algorithm for generalized k-server on uniform metrics. -/ def uniform_kserver_det_competitive (k : ℕ) {M : Fin k → Type*} [∀ i, DecidableEq (M i)] (A : List (∀ i, M i) → (∀ i, M i)) (a : ∀ i, M i) (γ : ℝ) : Prop := uniform_kserver_det_alg_serves A ∧ ∃ c : ℝ, ∀ ρ : List (∀ i, M i), (uniform_kserver_det_cost A a ρ : ℝ) ≤ γ * (uniform_kserver_opt k a ρ : ℝ) + c