OAI.UniformKServer.uniform_squared_logarithmic_main

The theorem states that UniformAlgorithmClaim holds, a defined proposition about the k-server problem in the explicit bit-machine model with rational metrics on n points. It asserts that there exist a single randomized bit machine M (a finite-control machine with an input tape, work tapes, an output stream, fair-coin transitions and a yield flag), natural numbers c>0 and e, and a real constant C>0 such that for every n and k with 3 ≤ n, 2 ≤ k and k < n, every rational metric d on Fin n, and every initial configuration s of the k servers, three things hold. Let L be the length of the standard self-delimiting binary encoding of (d,s). First, the deterministic boot phase, which runs M on that encoding for c(L+1)^e steps with all-false coins, ends in a yielded state. Second, at every reachable state after t requests (reachability ranges over every request and every assignment of coins, not just almost surely), serving the next request r with a coin budget of c(y+1)^e bits where y = L + ⌈log₂(t+2)⌉, yields a yielded state whose output, read as a binary number, is less than k, so the chosen server label is valid and nothing is repaired. Third, there is a constant B ≥ 0 such that for every finite request word w, the expected total movement cost of M, computed by averaging over all coin strings and charging d(server position, request) to the server selected by the output, is at most C(log(k+1))² times the offline optimal cost of serving w from s, plus B. The offline cost is the infimum over all choices of serving labels, with full knowledge of w.