AFTD Auto-Formalizing Theoretical Domains

uniform_kserver_det_competitive

def

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

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
See it in the graphDiscuss this resultChallenge it