The extended cost is absorbed at the antipode of the request
ProvedKServer.workFnU_growth_le_antipodeLet be the next request of a -server instance, in a metric space where has an antipode: a point with
so that the whole space lies on geodesics from to . Then the one-request increase of the work function is maximised at the configuration placing all servers at the antipode:
In other words, in a space with antipodes the extended cost of a request is realised at a single canonical configuration determined by the request alone.
Why the antipode does it
The Koutsoupias--Papadimitriou duality lemma says the extended cost is attained at any minimiser of the dual functional . In general, locating such a minimiser is itself work. But when has an antipode, the defining identity turns the dual functional inside out: , so
and minimising the right-hand side over is precisely what -Lipschitzness of the work function does at the point : the minimum is , attained at . So the all-antipodes configuration is automatically a dual minimiser --- no structure of the space beyond the antipode identity, and no information about , is needed --- and duality hands over the conclusion.
Role
This is the mechanism by which the Coester--Koutsoupias potential controls the extended cost. Their potential anchored at ends with the summand ; when the anchors can be chosen with the last summand is exactly , whose increase this theorem identifies as dominating the extended cost, while the remaining summands never decrease. The update property of the potential, hence -competitiveness of the Work Function Algorithm through the potential criterion, thus reduces to showing the minimum of the potential is attained at anchors ending at the request --- which is the content of their per-space analyses (multi-ray spaces, trees, the circle). Applied inside the antipodal extension of an arbitrary space, where every point has an antipode by construction, the hypothesis is automatic.
Formalization note
The antipode enters only through the stated identity; no involution, no extension structure, and no bound on the other distances of the space are assumed. is the constant configuration fun _ => rbar, and is workFnU, the work function of the unlabelled configuration.
import Mathlib import Definitions.Def_KServer_workfunctionU
namespace KServer
theorem workFnU_growth_le_antipode (k : ℕ) (hk : 1 ≤ k) (N : Type) [MetricSpace N]
(C₀ : Config k N) (σ : List N) (r rbar : N) (Δ : ℝ)
(hanti : ∀ y : N, dist y r + dist y rbar = 2 * Δ) (X : Config k N) :
workFnU C₀ (σ ++ [r]) X - workFnU C₀ σ X
≤ workFnU C₀ (σ ++ [r]) (fun _ => rbar) - workFnU C₀ σ (fun _ => rbar) := by sorry
end KServer