gen_k_server_uniform_is_rand_alg
Generalized k-server where each of the k servers moves in its own copy of the uniform metric on m points: configurations and requests are functions Fin k → Fin m. A real function P(past, r, x, y), taking a list past of earlier requests, the current request r, the current configuration x and a next configuration y, is a randomized online algorithm (in behavioural form) if for every past, r and x: P(past, r, x, y) ≥ 0 for every y, the sum over all y in Fin k → Fin m of P(past, r, x, y) is 1, and every y with P(past, r, x, y) ≠ 0 serves r, i.e. y i = r i for some i : Fin k. P(past, r, x, y) is the probability of moving from x to y when request r arrives after the requests past.
Statement
def gen_k_server_uniform_is_rand_alg {k m : ℕ} (P : List (Fin k → Fin m) → (Fin k → Fin m) → (Fin k → Fin m) → (Fin k → Fin m) → ℝ) : Prop
- Defined in
- arXiv:2610.37192, Sec. 2 (Preliminaries): randomized online algorithm for generalized k-server; here every space is the uniform metric Fin m and the algorithm is given in behavioural form by transition probabilities
- Verified
- 28 Oct 2026
- Axioms
- none listed
- Used by 4
- gen_k_server_uniform_one_server_competitive_oneWith one server (k = 1, configurations Fin 1 → Fin m) and any start configuration a, there are transition probabilities P with…
- gen_k_server_uniform_log_competitiveFor every k ≥ 1, every m and every start configuration a : Fin k → Fin m of generalized k-server on k uniform metrics with m points each…
- gen_k_server_uniform_expected_cost_fromGeneralized k-server on k uniform metrics with m points each: both configurations and requests are functions Fin k → Fin m (one point per…
- gen_k_server_uniform_competitiveGeneralized k-server on k uniform metrics with m points each: configurations and requests are functions Fin k → Fin m. With k m : ℕ…
Read back from the Lean
Given natural numbers k and m, a function P (which takes a history past : List (Fin k → Fin m), two configurations/states r, x : Fin k → Fin m, and a candidate next configuration y : Fin k → Fin m, and outputs a real number) satisfies gen_k_server_uniform_is_rand_alg if and only if: for all histories past and all r, x : Fin k → Fin m, the following three conditions hold:
1. For every y : Fin k → Fin m, P(past, r, x, y) ≥ 0;
2. The sum of P(past, r, x, y) over all y : Fin k → Fin m equals 1;
3. For every y : Fin k → Fin m, if P(past, r, x, y) ≠ 0, then there exists an index i : Fin k such that y(i) = r(i).
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
/-- Randomized online algorithm for generalized k-server on k uniform metrics `Fin m`, given by transition probabilities `P past r x y` (earlier requests, current request, current configuration, next configuration); the next configuration must serve the request. -/ def gen_k_server_uniform_is_rand_alg {k m : ℕ} (P : List (Fin k → Fin m) → (Fin k → Fin m) → (Fin k → Fin m) → (Fin k → Fin m) → ℝ) : Prop := ∀ (past : List (Fin k → Fin m)) (r x : Fin k → Fin m), (∀ y, 0 ≤ P past r x y) ∧ (∑ y, P past r x y) = 1 ∧ (∀ y, P past r x y ≠ 0 → ∃ i, y i = r i)