Tight Bounds for Randomized Generalized $k$-Server on Uniform Metrics

Junho Hwang

Source-linked AI summary

Tight Bounds for Randomized Generalized $k$-Server on Uniform Metrics

Junho Hwang

arXiv:2610.37192v1Oct 27, 2026cs.DS

TL;DR

In generalized k-server, each server moves in its own metric space, and a request is served when some server reaches its designated point. The paper determines randomized competitive ratios on uniform metrics, establishing Θ(k log k) for unit distances and exp(Θ(k)) with weights.

Problem
The paper asks for randomized competitive ratios for generalized k-server on uniform metrics, improving prior unit-distance bounds.
Source: §1.1 · p. 3
Method
The algorithms update weights on configurations and use couplings to control the movement of the real servers.
Source: §1.2 · pp. 3, 6
Results
Θ(k log k) is the randomized competitive ratio on unit-distance uniform metrics, and exp(Θ(k)) is the ratio on weighted uniform metrics.
Source: §1.1 · p. 3
Takeaways & Limitations
The unit-distance leading constant remains between 1/20 and 1, while the weighted exponent base remains between 2 and 20.
Source: §6 · p. 21
The guarantees are against an oblivious adversary, with the request sequence fixed in advance.
Source: §3.2 · p. 9

Abstract

from arXiv · show

In the generalized $k$-server problem, each of $k$ servers moves in its own metric space, and a request $(r_1,\dots,r_k)$ is served once some server $i$ stands at the point $r_i$ of its space. We determine the randomized competitive ratio against an oblivious adversary when every space is a uniform metric. With unit distances the ratio is $\Theta(k\log k)$: we give a $(k+1)\ln(2k)$-competitive algorithm and show that for large $k$ every algorithm has ratio at least $\frac{1}{20}k\ln k$, improving the bounds $O(k^2\log k)$ and $\Omega(k)$ of Bienkowski, Je\.z, and Schmidt. When server $i$ pays $w_i$ per move, the ratio is $\exp(\Theta(k))$: we give a $20^k$-competitive algorithm, which also applies to weighted $k$-server on uniform metrics. This improves the $\exp(O(k^2))$ bound of Bijoy, Mondal, and Chiplunkar and matches the $\Omega(2^k)$ lower bound of Ayyadevara and Chiplunkar up to the base of the exponent. Both algorithms follow normalized weights exactly, through couplings whose expected movement is controlled by the decrease of the logarithm of the total weight. The lower bound hides a random permutation among the solutions of random permutation constraints, which split into small, well-separated components, and then forbids one position to one server at a time.

1 Introduction

The paper determines randomized competitive ratios for generalized k-server on uniform metrics, with Θ(k log k) for unit distances and exp(Θ(k)) with weights. Its algorithms follow normalized weights, while its unit-distance lower bound uses random permutation constraints whose solutions split into separated components.

1.1 Our results

The unit-distance upper bound improves the prior upper bound by a factor of k, while the lower bound improves the prior Ω(k) bound by a factor of log k.The lower-bound construction uses k points per space, compared with two points per space in the earlier construction.Source: §1 · p. 2, §1.1 · p. 3

1.2 Techniques

Unit-distance algorithms distribute weight over configurations, pass part of a failing configuration’s weight to its one-server repairs, and follow the normalized weights exactly.Expected movement is bounded by (k + 1) times the decrease in the logarithm of total weight; the total bound is OPT · ln(2k).Source: §1.2 · p. 3, Figure 1 · p. 4
The unit-distance adversary hides a random permutation among many feasible solutions, then forbids one position for one server at a time to eliminate distant components.The setup constraints produce e^(Ω(k log k)) solutions in components separated by more than 0.77k; over a phase, the algorithm pays at least 1/20 k^2 ln k in expectation while OPT pays at most k.Source: §1.2 · pp. 4–5, Figure 2 · p. 5
For weighted metrics, exponential weights and maximal coupling select and switch among runs, yielding a 20^k-competitive algorithm after rounding the weights.The analysis bounds the recursive phase constants by c_k ≤ 10 · 5^(k−1), then accounts for the offline bound and weight rounding.Source: §1.2 · p. 6

1.3 Related work

Generalized k-server on uniform metrics is a metrical service system on the product space; the cited general-metric competitive algorithms cover only k = 2.The paper situates its results alongside work on metrical service systems and randomized k-server on other metric classes.Source: §1 · p. 1, §1.3 · p. 6

2 Preliminaries

The problem models each server as moving in its own metric space, with requests served when some server reaches its designated point. Its preliminaries define configurations, movement cost, and a lazy offline comparator.

A configuration is a tuple of server positions, one coordinate per metric space.Source: §2 · p. 6
A request is served when at least one server occupies its designated point, and an online algorithm must move to a serving configuration.Source: §2 · p. 7
The randomized competitive guarantee is evaluated on request sequences fixed in advance, against an oblivious adversary.Source: §2 · p. 7
An offline solution is lazy when it stays put if its current configuration serves the request and otherwise moves one server to a repair.Source: §2 · p. 7
With unit weights, an offline solution of cost C can be replaced by a lazy one from a that moves at most C + d(a, o0) times.Source: §2 · p. 7

3 An O(k log k)-competitive algorithm for unit weights

The unit-weight algorithm updates weights on configurations and follows their normalized distribution, with expected movement controlled by the decrease in total weight. The method extends to set-valued requests, yielding guarantees for paging and metrical service systems.

3.1 The weight update

A failing configuration passes 1/(2k) of its weight to each one-server repair, while configurations serving the request retain their weight.The update defines the new normalized distribution over configurations.Source: §3.1 · p. 8

3.2 The algorithm

The algorithm preserves the normalized weight distribution and has expected movement at most (k + 1) ln(Φt−1/Φt) per request.When the current configuration fails, it chooses a random repair or resamples from the updated distribution.Source: §3.2 · pp. 8–9
E[ALG(ρ)] ≤ (k + 1) ln(2k) · OPT(ρ) for unit-weight requests, by charging movement to the decrease in total weight and comparing against a lazy offline solution.A lazy solution moving m times retains weight at least (2k)^−m.Source: §3.2 · p. 9

3.3 Requests that specify sets

For requests specifying at most B points in total, the algorithm achieves E[ALG(ρ)] ≤ (k + 1) ln(2B) · OPT(ρ).It uses all one-server moves to a requested point as repairs.Source: §3.3 · p. 9
The set-request guarantee gives paging with heterogeneous cache slots a ratio of (k + 1) ln(2k), improving its previous O(k^2 log k) bound.For metrical service systems with requests of at most ℓ points, the ratio is (k + 1) ln(2kℓ), versus the previous O(k^3 log ℓ) bound when ℓ ≥ 2.Source: §3.3 · pp. 9–10

4 An Ω(k log k) lower bound for unit weights

This section proves an Ω(k log k) lower bound for unit weights using a random feasible permutation and an adversary that forbids one position at a time, forcing substantial expected movement. Across L phases, the algorithm’s expected cost is at least (1/20)Lk² ln k while OPT costs at most Lk.

4.1 Permutation constraints

A configuration serves all k + hk setup requests exactly when it is a permutation accepted by every family in F, that is, when it lies in Q(F).The initial k requests enforce that the configuration is a permutation; each family contributes hk further requests.Source: §4.1 · p. 10

4.2 Two moments

For large k, E0[Z^2] ≤ e^5k(E0Z)^2; moreover, ln E0Z is at least εk ln k − k and at most εk ln k + k.Source: §4.2 · p. 11

4.3 Components of the feasible set

A good system has at least E0Z/2 feasible permutations, while its components are more than βk coordinates apart and each has fewer than 2^k configurations.Each component varies in fewer than ηk coordinates and satisfies Σ_i(|Ai(C)| − 1) < k.Source: §4.3 · p. 13

4.4 Requests that forbid one position

A random request that forbids one position eliminates a given component with probability at least (β −η)/(k −1).The request is sampled uniformly among pairs (i, a) for which the hidden permutation has σ_i ≠ a.Source: §4.4 · p. 14

4.5 The posterior of the hidden permutation

After t forbidden-position requests, the hidden permutation is uniform on Qt, and 2^k E[1/|Qt|] ≤ e^−2k for large k.Qt is the set of feasible permutations serving the setup requests and the first t requests.Source: §4.5 · p. 14

4.6 The adversary

For large k, the expected cost of ALG during each phase is at least (1/20)k^2 ln k; each confinement sequence is computed from ALG’s distributions, never its random choices.Source: §4.6 · p. 15
(1/20)Lk^2 ln k is the expected algorithm cost lower bound, versus OPT ≤ Lk, implying a competitive ratio of at least (1/20)k ln k as L grows.The offline solution moves to that phase’s σ at its first request and stays there; averaging the competitive guarantee over the finite input distribution and letting L → ∞ gives the ratio bound.Source: §4.6 · pp. 15–16

5 A 20k-competitive algorithm for weighted uniform metrics

The section combines nested request phases, randomized aggregation, and an offline lower bound to prove a 20^k-competitive algorithm for weighted uniform metrics. Its analysis also handles arbitrary weights and space cardinalities.

5 A 20^k-competitive algorithm for weighted uniform metrics

The proof builds on the phases of Bijoy, Mondal, and Chiplunkar [BMC26], supplies complete proofs for generalized requests, and replaces their virtual-algorithm following rule with aggregation.Demand is counted separately in every coordinate.Source: §5 · p. 16

5.1 Phases

A completed level-ℓ phase selects high-demand points during exploration, then runs parallel exploit parts for those points.The phase demand has norm κℓ in each coordinate; a completed multiphase has norm mℓκℓ.Source: §5.1 · p. 17

5.2 Aggregating parallel runs

A randomized master follows active simulated phase strategies, and the expected movement bound depends on the decrease in total expert weight.The master couples consecutive normalized expert distributions and bounds switching movement using total variation.Source: §5.2 · p. 18

5.3 Phase strategies

The phase strategy serves accepted requests while moving only servers 1 through ℓ, with expected cost at most cℓvℓ.For an (ℓ, U)-multiphase, the expected cost is at most cℓvℓ+1.Source: §5.3 · p. 18

5.4 The offline lower bound

Every completed (k, ∅)-phase costs any offline solution at least v_k/2^k, supplying the lower bound used to analyze the algorithm.The proof obtains this by showing that every solution for a level-k phase is not contaminated and applying the level-dependent cost bound.Source: §5.4 · pp. 19, 21

5.5 Proof of Theorem 1.3

20^k is the multiplicative factor in the weighted guarantee, which also has additive term 10^k w_k.The algorithm runs phase strategies and rounds weights before applying the final bound.Source: §5.5 · p. 21

6 Concluding remarks

The paper determines the randomized ratios for generalized k-server on uniform metrics: Θ(k log k) with unit distances and exp(Θ(k)) with weights. It closes with open questions about constants, space size, and efficient algorithms.

6 Concluding remarks

The randomized competitive ratios are Θ(k log k) for unit distances and exp(Θ(k)) for weighted uniform metrics.The leading constant in the unit-distance bounds remains between 1/20 and 1, and the weighted exponent base between 2 and 20.Source: §6 · p. 21
The unit-distance lower bound uses k-point spaces, leaving the ratio as a function of both k and points per space open.The cited Ω(k) bound of [BJS19] uses only two points per space.Source: §6 · p. 21
The algorithms maintain very large distributions, and polynomial-time algorithms remain an open direction.The paper also notes that no f(k)-competitive deterministic algorithm is known on general metrics for k ≥ 3.Source: §6 · p. 21

AI usage disclosure

The author reports using AI agents for exploratory proof discussions and manuscript drafting and revision, while taking full responsibility for the paper.

AI usage disclosure

AI agents were used for exploratory discussions during proof development.The author states that they take full responsibility for the paper’s contents and correctness.Source: AI usage disclosure · p. 22
AI agents also assisted with drafting and revising the manuscript.The disclosure separately identifies this use alongside exploratory discussions.Source: AI usage disclosure · p. 22
The author takes full responsibility for the paper’s contents and correctness.This responsibility statement accompanies the disclosure of AI assistance.Source: AI usage disclosure · p. 22