An online $k$-server algorithm maintains $k$ points of a metric space, the servers, and reacts to a stream of requests in the same space, one request at a time. Every request names a point; the algorithm moves a single server to that point, pays the metric distance of the move, and leaves the other $k-1$ servers in place. A request to a point already occupied by a server costs zero. The offline optimum for a finite request word is the cheapest total movement achievable by a service that reads the whole word first. For a constant $c$, the algorithm is $c$-competitive if, for every finite request word chosen independently of the algorithm's random bits (the oblivious-adversary model), its expected movement is at most $c$ times the offline optimum plus an additive term independent of the length of the word. Manasse, McGeoch, and Sleator introduced the problem in this form as a metric abstraction of paging and of related service questions.
./manasse-mcgeoch-sleator-1990-competitive-algorithms-for-server-problems.pdf
Paging is the uniform-metric special case: servers model the pages currently held in a cache, the request stream is a sequence of pages, and a request to an absent page costs one unit of movement. Fiat, Karp, Luby, McGeoch, Sleator, and Young proved that the randomized marking algorithm attains competitive ratio $2H_k$ on this metric, where $H_k = 1 + 1/2 + \dots + 1/k$ is the $k$th harmonic number, and that no randomized algorithm attains ratio $H_k$ against an adaptive adversary. Logarithmic behaviour of a natural metric suggested the randomized $k$-server conjecture, which proposed an $O(\log k)$ ratio on every finite metric, and the marking idea seeded many potential-based and phase-based devices that later spread through online computation.
./fiat-karp-luby-mcgeoch-sleator-young-1991-competitive-paging-algorithms.pdf
Bubeck, Coester, and Rabani settled the randomized $k$-server conjecture in the negative by exhibiting finite metrics on which every randomized online algorithm has competitive ratio at least $\Omega(\log^2 k)$. The scale $\log^2(k+1)$ appearing in Theorem 1 is therefore sharp: no randomized algorithm uniform over all finite metrics can do better in order.
./bubeck-coester-rabani-2211.05753-randomized-k-server-conjecture-false.pdf
Independently, Coester and Cosson obtained a polynomial-time randomized algorithm with ratio $O(\log^2 k)$ on sufficiently separated hierarchically separated trees and ratio $O(\log n \log^2 k)$ on arbitrary $n$-point metrics, with request-processing time that is polynomial in the input and independent of the length of the request word. On trees that algorithm uses only $O(\log k)$ fresh random bits in total; on general metrics it uses a bounded initial budget of random bits also independent of the length. Those guarantees are strictly stronger in time and randomness than the ones obtained by the construction below. The setting is different: total time and total randomness are left unconstrained, and the structural condition under which the log-squared ratio can be computed uniformly from any finite rational metric is the object of study, with the additive movement constant unrestricted and with per-request time allowed to grow with the binary length of the request counter.
./coester-cosson-2605.01497-randomized-k-server-in-polynomial-time.pdf
The mathematical input is the companion existence theorem. For every integer $k \ge 2$, every finite metric space with at least $k+1$ points, and every distinct starting tuple $u$ of length $k$, there exists a single randomized online policy whose expected movement against any finite request word $w$ chosen independently of its random bits satisfies
$$ \mathbb{E}[\mathrm{cost}_{A,u}(w)] \le C_0 \log^2(k+1)\, \mathrm{OPT}_u(w) $$
for an absolute constant $C_0 < \infty$. Only existence is available: neither the policy's transition probabilities nor any procedure that evaluates them is furnished. The task is to convert that existence assertion, which prescribes no procedure, into a single algorithm that is uniform on all finite rational metrics, has polynomial preprocessing, and admits per-request bit complexity depending only on the input plus the binary expansion of the request counter.
./companion.pdf
THEOREM 1. There are an absolute constant $C < \infty$ and a polynomial $p$ with the following property. Let $n \ge 3$, $2 \le k < n$, let $d$ be a rational metric on $X = \{1, \dots, n\}$, and let $s \in X^k$ be a labeled starting tuple, repetitions permitted. Let $L$ be the total binary encoding length of $n$, $k$, $d$, and $s$ under a fixed canonical encoding. There is a single randomized online algorithm, defined by a fixed finite-alphabet bit machine that reads $(n, k, d, s)$ on its input tape, with three properties. Preprocessing uses at most $p(L)$ bit operations. At request $r_t$, for every reachable history and internal state, the algorithm uses at most $p(L + \lceil \log_2(t+1) \rceil)$ additional bit operations, draws only unbiased random bits, and moves exactly one chosen server to the requested point, permitting the move to have length zero. For every finite request word $\sigma$ independent of the algorithm's random bits,
$$ \mathbb{E}[\mathrm{cost}_{A,s}(\sigma)] \le C \log^2(k+1)\, \mathrm{OPT}_s(\sigma) + B_{d,k,s}, $$
where $B_{d,k,s} < \infty$ depends only on the instance and $C$ is absolute. The algorithm is not told the length of $\sigma$ in advance.
Two features of the statement are essential. There is no bound on the additive term $B_{d,k,s}$: it may be enormous for a given instance, and it absorbs a delay during which the prescribed policy has not yet been activated. The permitted per-request computation grows polynomially in the binary expansion of the request counter, not in $L$ alone. Both features are forced by the schedule that follows from the construction, and serve to separate this algorithm from polynomial-time algorithms whose per-request cost is bounded by a function of $L$ only.
./coester-cosson-2605.01497-randomized-k-server-in-polynomial-time.pdf
The argument replaces the existence theorem by a terminating computation, then wraps that computation inside a schedule whose cost grows only with the binary length of the request counter. Two devices carry the weight. The first is a finite linear-algebraic description of a strongly lazy policy: from configuration probabilities and one-step transition flows, exact rational elimination yields a decision table whose dyadic conditional rows can be sampled with a bounded number of unbiased bits and whose expected movement exceeds the optimum by a multiplicative coefficient bounded by $C_0 \log^2(k+1)$ up to a bounded additive loss. The second is a universal filter keeping the table's input word short, combined with a deterministic marking fallback that takes over once the table has made too many positive moves inside the current epoch. Both devices act on request words determined by the raw input alone, so the analytic estimate always applies to a fixed word even when the algorithm's own mode switches at a random time.
./companion.pdf
The first step is lazification. A service is strongly lazy if, on a request to a point that already holds a server, it moves that server by zero length, and on a request to a point unoccupied by servers it moves exactly one server to that point. From a distinct starting tuple, a strongly lazy service keeps the server positions distinct for all time. Manasse, McGeoch, and Sleator observed that every online policy has a strongly lazy follower whose total cost on every finite word is no larger, path by path, against every realization of the original randomness; the argument uses a matching potential between follower tuple and virtual tuple and the triangle inequality. The follower's decisions depend only on the revealed request and the currently simulated state, so the construction is causal. Consequently the existence theorem may be assumed without loss of generality to promise a strongly lazy policy from any distinct start.
./manasse-mcgeoch-sleator-1990-competitive-algorithms-for-server-problems.pdf
Proof. Simulate the original policy as a virtual process. Let $c$ denote the follower tuple and $v$ the virtual tuple, and put $\Phi(c, v) = \min_{\pi \in S_k} \sum_{j=1}^k d(c_j, v_{\pi(j)})$, where $S_k$ is the symmetric group on $k$ letters. This is the cheapest perfect matching between the two tuples; the minimum is a finite minimum over permutations and exists even if the virtual tuple repeats positions. Initially $\Phi(c, v) = 0$. Suppose the virtual policy just served request $r$ at cost $\eta$, taking $v$ to $v'$. Applying the triangle inequality to a previously minimizing matching gives $\Phi(c, v') \le \Phi(c, v) + \eta$. If $c$ already covers $r$, the follower moves zero length. Otherwise fix a minimizing matching between $c$ and $v'$ together with a virtual label at $r$, move the matched follower label to $r$ at cost $m$, and obtain $c'$. The matching edge from that follower label to its partner at $r$ decreases from length $m$ to zero while all other edges keep their length, so $\Phi(c', v') \le \Phi(c, v') - m$; combined with the previous bound, $m + \Phi(c', v') \le \Phi(c, v) + \eta$. Summing this inequality over the requests of any finite word and using that the potential is zero initially and nonnegative at the end gives total follower cost at most total virtual cost. Because the follower moves only at requests not already covered by its own tuple, its positions remain distinct whenever the initial tuple is distinct. All decisions used only the revealed request and the currently simulated state, so the construction is causal.
./manasse-mcgeoch-sleator-1990-competitive-algorithms-for-server-problems.pdf
The second step is a finite flow system. Fix the metric on $X = \{1, \dots, n\}$ and define $D = \max_{x,y} d(x,y)$, $\delta = \min_{x \ne y} d(x,y)$, so $0 < \delta \le D$. Fix a distinct initial tuple $u = (1, \dots, k)$, even when the true starting tuple $s$ may repeat points. For a prescribed horizon $H$, let $\mathcal{C}$ be the set of ordered $k$-tuples of distinct points of $X$, and let $T(c, r, j)$ denote the tuple obtained from $c$ by replacing its $j$th coordinate with $r$. The allowed-label set is $J(c, r) = \{j : c_j = r\}$ when $r$ belongs to $c$, and $J(c, r) = \{1, \dots, k\}$ otherwise. Introduce unknowns $p_{w,c}$ for the probability of configuration $c$ after the finite word $w$, unknowns $f_{w r, c, j}$ for the joint probability that configuration $c$ is used before the next request $r$ and label $j$ serves it, and one coefficient $a$. The defining constraints are
$$ p_{w,c} \ge 0, \quad \sum_c p_{w,c} = 1, \quad p_{\varnothing, c} = [c = u], $$
$$ f_{w r, c, j} \ge 0, \quad \sum_{j \in J(c,r)} f_{w r, c, j} = p_{w,c}, $$
$$ \sum_{\substack{c \in \mathcal{C},\ j \in J(c,r) \\ T(c,r,j) = c'}} f_{w r, c, j} = p_{w r, c'}, $$
for every word $w \in X^{\le H}$, $|w| < H$, request $r \in X$, and configuration $c' \in \mathcal{C}$, together with a coefficient constraint $a \ge 0$ and one inequality per nonempty word $x = r_1 \dots r_h$ with $h \le H$:
$$ \sum_{i = 1}^h \sum_{c \in \mathcal{C}} \sum_{j \in J(c,r_i)} f_{r_1 \dots r_i, c, j}\, d(c_j, r_i) \le a\, \mathrm{OPT}_u(x). $$
$\mathrm{OPT}_u(x)$ denotes the offline minimum for the word $x$ from the tuple $u$; it is computable by a finite dynamic program over the finitely many tuples of $X^k$ reachable from $u$. Explicitly, let $\Gamma_w(c)$ be the minimum cost of serving $w$ from $u$ and finishing at tuple $c$, with $+\infty$ marking an unreachable tuple; start with $\Gamma_{\varnothing}(u) = 0$ and all other entries $+\infty$, and use
$$ \Gamma_{w r}(c') = \min_{\substack{c \in X^k,\ 1 \le j \le k \\ T(c, r, j) = c'}} (\Gamma_w(c) + d(c_j, r)), \qquad \mathrm{OPT}_u(w) = \min_{c \in X^k} \Gamma_w(c). $$
These recurrences use only rational arithmetic and comparisons and never divide by $\mathrm{OPT}_u(x)$; a word with zero optimum gives a zero right-hand side in the coefficient constraint. Finite-horizon linear descriptions of randomized $k$-server strategies in exactly this marginal-and-flow form appear in Moemke's competitive-ratio approximation scheme on fixed finite metrics.
./moemke-1303.2963-competitive-ratio-approximation-scheme.pdf
The system is feasible and bounded: by the existence theorem and lazification, a real solution exists with $a = C_0 \log^2(k+1)$, obtained from the probability distribution of the source policy. Since all coefficients are rational, the feasible set for $a$ after projecting out the $p$ and $f$ variables is a nonempty half-line $[a_*, \infty)$ with rational endpoint $a_*$. To compute $a_*$ exactly, replace each equality by a pair of weak inequalities, eliminate all variables except $a$ one at a time by Fourier-Motzkin elimination, and reverse the eliminations by choosing the largest lower bound at each variable. To eliminate a variable $z$, divide every inequality in which $z$ occurs by the (nonzero) rational coefficient of $z$, split the resulting affine bounds into lower bounds $z \ge L_i(y)$ and upper bounds $z \le U_j(y)$, keep all inequalities independent of $z$, and add every comparison $L_i(y) \le U_j(y)$; if either family is empty, add nothing. This is an exact existential projection. Each elimination removes one variable and a finite set of inequalities, so starting from finitely many the procedure terminates after finitely many eliminations. After all eliminations, the feasible $a$-values are given by finitely many weak rational inequalities in one variable. That set is nonempty because the real solution already exhibited belongs to it, and it includes the constraint $a \ge 0$, so its least value is the maximum of finitely many rational lower bounds. That maximum is rational and belongs to the feasible set. Compute it, then reverse the eliminations one variable at a time. At each reversal, evaluate the already-computed values inside the bounds and choose the largest lower bound if one exists; otherwise choose the smallest upper bound if one exists; otherwise choose zero. The projection inequalities ensure that the chosen value also respects any upper bounds. Repeating this yields a rational solution of the full system. Because both the Fourier-Motzkin step and the back-substitution work with rationals, the coefficient $a$ computed this way is a rational number satisfying $0 \le a_* \le C_0 \log^2(k+1)$; neither $C_0$ nor the source policy enters the computation. The elimination and its dual were introduced by Dantzig and Eaves in 1973; Subramani's exposition documents the step-by-step algorithm.
./subramani-wvu-fourier-motzkin-elimination-notes.pdf
From the rational solution, define causal conditional rows by $q_{w, r, c}(j) = f_{w r, c, j} / p_{w,c}$ when $p_{w,c} > 0$, and put all mass on the smallest allowed label when $p_{w,c} = 0$. Each row is a rational probability distribution supported on the allowed labels $J(c,r)$, including rows at configurations the unrounded policy does not reach. Along a fixed word $w$, induction using the mass, outflow, and inflow constraints shows that the causal policy generated by these rows has exactly the marginals $p$ and $f$, and therefore that the flow system's coefficient constraint is the expected-cost bound. Rounding follows. Fix $b$ the least nonnegative integer with $2^b \ge k H^2$. In each row reserve its smallest allowed label $j_0$ and set $\widehat q_{w,r,c}(j) = 2^{-b}\lfloor 2^b q_{w,r,c}(j) \rfloor$ for $j \ne j_0$, with the residual mass $\widehat q_{w,r,c}(j_0) = 1 - \sum_{j \ne j_0} \widehat q_{w,r,c}(j)$. The new row is supported on $J(c,r)$ and its total variation distance from the original is at most $k 2^{-b}$. Sampling with $b$ unbiased bits, using the numerators of the row with common denominator $2^b$, uses exactly $b$ random bits per decision and requires no rejection loop. Coupling the rounded and unrounded causally generated services until their first differing label choice, on a word of length $h \le H$, gives discrepancy probability at most $h k 2^{-b}$, since at any agreeing step the conditional discrepancy probability is at most $k 2^{-b}$. On the complement the two costs are equal; on the discrepancy event the difference is at most $h D$. Hence the expected movement of the rounded table from $u$ on any word $w$ of length $h \le H$ satisfies
$$ \mathbb{E}[\mathrm{cost}_{\mathcal{T}_H, u}(w)] \le a\, \mathrm{OPT}_u(w) + k h^2 2^{-b} D \le a\, \mathrm{OPT}_u(w) + D. $$
A rounded trajectory can reach a configuration whose unrounded marginals were zero. That possibility causes no exception, because the table has already assigned such a configuration a legal row and reaching it can only occur after a discrepancy, whose cost is already absorbed.
For every positive integer $H$ there is a terminating deterministic procedure on rational input that constructs a rational number $a$ and a finite table defining a strongly lazy policy $\mathcal{T}_H$ from $u$ such that $0 \le a \le C_0 \log^2(k+1)$ and
$$ \mathbb{E}[\mathrm{cost}_{\mathcal{T}_H, u}(w)] \le a\, \mathrm{OPT}_u(w) + D $$
for every word $w$ with $|w| \le H$. Every decision of the table uses exactly $b = \lceil \log_2(k H^2) \rceil$ independent unbiased bits. Neither $C_0$ nor an oracle for the existence theorem is required. The procedure's running time is not bounded at this stage; what matters is termination and output size, since scheduling intervenes before the constructor is put online.
A fixed table horizon does not by itself serve an unbounded stream: a long interval may contain many requests while the offline optimum hardly grows. To hold the table's input word short, partition the suffix being served into raw blocks: a block ends at the request that first raises the number of distinct requested points in that block to $k+1$, and the next request begins a new block. Every completed block forces any service to pay at least $\delta$ inside the block, since the entering $k$ server locations cannot cover all $k+1$ distinct requested points. Set $R = \lceil k D / \delta \rceil$ and let an epoch consist of $R$ completed raw blocks. A completed epoch then forces cost at least $R \delta \ge kD$, and this lower bound covers the cost of restarting the table between epochs. A finite input may end inside a block or on a block boundary; every nonempty epoch contains at most $R$ nonempty blocks, counting a final incomplete block. Both block and epoch boundaries depend only on the raw request word and can be recognized on the fly.
The cap parameters are fixed by the instance. Set $F = R (k+1) D$, $M = \lceil F / \delta \rceil$, and $H = \sum_{i = 0}^{M} k^i$. Anticipating a marking fallback that spends at most $(k+1) D$ per block, $F$ reserves the fallback's worst-case cost for a whole epoch. A table trajectory that makes $M+1$ positive moves inside an epoch has already paid $M \delta \ge F$, which is enough to finance a fallback for the remainder of the epoch. The tree bound $H$ counts the capped table trajectories to be tracked by the filter below.
The filter works on one epoch at a time. At the start of the epoch, initialize a list with the single entry $(u, 0)$. Each entry $(c, i)$ consists of a distinct-position labeled tuple $c$ and a nonnegative move count $i$; several entries with identical data are allowed to coexist. On each raw request $r$ apply two deterministic rules. If every listed tuple covers $r$, drop the request and leave the list unchanged (this rule applies in particular to an empty list). Otherwise keep $r$: preserve entries that cover $r$; for every other entry $(c, i)$ with $i < M$, replace it by the $k$ entries $(T(c, r, j), i+1)$ for $j = 1, \dots, k$; an entry with $i = M$ is removed without replacement. The word of kept requests is built up as the epoch unfolds. The filter runs on every raw request, in either mode and either fate of the algorithmic service, and uses no random bits. This filtering-and-resetting device parallels Mikkelsen's phase construction for finite lazy task systems, in which candidate policies are simulated together, requests that are universally free to all candidates are discarded, and a bounded cost cap triggers a fallback; the branching-tree version below makes the bounds on retained word and on state explicit.
./mikkelsen-1511.05886-randomization-glimpse-future.pdf
After any raw prefix, the filter's live list represents exactly the endpoint tuples and move counts of all strongly lazy services from $u$ of the current kept word that use at most $M$ positive moves. The assertion is by induction. A dropped request does not change the kept word; a kept request preserves entries that cover $r$, and splits each noncovering entry into the $k$ possible single-move children (or discards it once the cap has already been reached). Strong laziness at a distinct tuple forces at least one positive move on any request not covered by that tuple, and every strongly lazy service from a distinct start remains at distinct tuples, so the filter's entries are exactly the trajectories of strongly lazy services that have not yet exceeded the cap. Hierarchically, give the initial entry a root and, whenever an entry is spent, give each child a distinct new node. The resulting rooted tree branches at most $k$-way and has depth at most $M$, hence at most $H$ nodes total. A hit keeps the same node, a spent node never returns, and every kept request spends at least one previously unspent node. Consequently over any epoch the filter creates at most $H$ entries and its live list and its kept word each have size at most $H$, regardless of the number of raw requests. This bound includes the request that might empty the list; every later request of that epoch is then dropped. The quantifier over all strongly lazy services is important, because the list also contains every legal trajectory of the rounded table within the move cap, including trajectories that visit a configuration having zero unrounded probability.
Virtual service inside an epoch has two modes, initially table mode. It carries a virtual tuple starting at $u$ and a positive-move counter starting at zero. Every virtual label choice is simultaneously the actual algorithm's choice: the actual labeled server is moved to the request, the other servers stay put, and actual positions are never reset. In table mode, feed each kept request to the table, keyed by the kept prefix before that request and the current virtual tuple, drawing fresh unbiased bits from a shared block. On a dropped request choose the virtual label occupying that point and pay nothing. Increment the counter on any table-mode move to an unoccupied point; if the counter reaches $M + 1$ after a request, enter fallback mode for the remainder of the current epoch. By the filter lemma, the virtual tuple before a table-mode request is a legal trajectory of the table on the kept prefix with counter at most $M$, and the lemma also guarantees that no table decision beyond horizon $H$ is ever requested. In particular an empty list cannot cause an uncovered dropped request in table mode, since table mode only faces kept requests, and every kept request of a strongly lazy trajectory that has not exceeded its cap remains among the listed entries.
./mikkelsen-1511.05886-randomization-glimpse-future.pdf
In fallback mode, the marking discipline of paging replaces the table for the remainder of the epoch. Empty the mark set on entry to fallback and again at each subsequent raw-block start. Every mark is assigned a distinct label, kept at that marked point until the block ends. Rules, with all ties resolved by the smallest label. At a raw-block endpoint, choose a virtual label covering the point if one exists, else any virtual label; serve the request and discard the marks. At any other request, if the point is marked, choose its assigned label; if it is unmarked, choose a virtual label covering the point if one exists, else choose a label not currently assigned to a mark; serve the request, mark its point, and assign the chosen label to it. An already-covering label at a new point is unassigned, since labels assigned to previous marks remain at those different points, and the virtual rules therefore always preserve distinct positions. On a nonendpoint request at a newly marked point, the raw block contains at most $k$ distinct points through that request, so the number of already-existing marks is fewer than $k$, and an unassigned label always exists; no movement at a nonendpoint disturbs a previously assigned label, so repeated marked requests are free. At most $k$ distinct nonendpoint points occur in any raw block, and each costs at most $D$ on its first fallback appearance; the endpoint, if served in fallback, costs at most one further $D$. The remaining portion of any block therefore costs at most $(k+1) D$ in virtual distance, and an incomplete final block has no endpoint cost. At most $R$ block portions remain in the epoch, so the total virtual cost of fallback over the rest of the epoch is at most $F = R(k+1) D$, including when the input ends inside a raw block. The request on which the switch is triggered belongs entirely to table mode and is not counted. Both the mark rules and this cost bound go back to the paging marking algorithms of Fiat, Karp, Luby, McGeoch, Sleator, and Young, whose protection of marked points gave the first sharp phase-based accounting in competitive online computation.
./fiat-karp-luby-mcgeoch-sleator-young-1991-competitive-paging-algorithms.pdf
Raw-block and completed-block counters are updated using every raw request, independently of the current mode and the filter. If the switch happens at a block endpoint, fallback marks start empty in the next block (if any). If it happens at an epoch endpoint, no fallback remainder occurs in that epoch. In every case the next epoch begins in table mode with fresh virtual tuple and fresh filter. These are changes of internal state only and require no knowledge of when the input ends. Thus the routine is causal even though its mode switches at a random time. The phase-based cost accounting that accompanies these resets is of the kind used in Moemke's bounded-sequence reduction and in the bounded-cost phase methods of Komm, Kralovic, Kralovic, and Moemke for randomized online algorithms with high-probability guarantees.
./moemke-1303.2963-competitive-ratio-approximation-scheme.pdf
./komm-kralovic-kralovic-moemke-1302.2805-randomized-online-computation-high-probability-guarantees.pdf
Two estimates close the movement analysis: one per epoch, and one over the number of epochs. Fix a finite request word $\sigma$ independent of all random bits, and fix the deterministic index at which the routine begins. Choose one optimal labeled service of the whole word starting from $s$. For each nonempty epoch $E$, including its possibly truncated final portion, let $O_E$ be that service's movement during $E$ and let $w_E$ be the filter's full kept word in $E$. Both the epoch boundaries and $w_E$ depend only on the raw request word, hence are deterministic.
The epoch estimate reads: for every such epoch, from any actual entering tuple, the expected actual cost in that epoch satisfies
$$ \mathbb{E}[\mathrm{cost}_{\rm actual}(E)] \le 2 a\, O_E + (2a+2) k D. $$
The bound is uniform in the actual entering tuple.
The proof is by shadowing. Run a shadow copy of the table from $u$ on the full word $w_E$, and let $V_E$ be its cost. More precisely, assign independent blocks of $b$ unbiased bits to the successive positions of that deterministic word; use the same blocks for the actual table-mode decisions and reserve later blocks for the shadow's analysis of what would have happened had the algorithmic service not switched. Dropped requests leave the table-mode tuple unchanged, so the shadow and the virtual service agree through every table-mode decision, including the triggering move that takes the positive-move count to $M+1$. The shadow therefore has the ordinary full-table law, without conditioning on whether or when the switch occurs. By the finite-table proposition and by the filter lemma, which bounds the length of $w_E$ by $H$,
$$ \mathbb{E}[V_E] \le a\, \mathrm{OPT}_u(w_E) + D. $$
Table-mode cost is at most $V_E$. If there is a switch, its common prefix already contains $M+1$ positive moves of length at least $\delta$ each, so $V_E \ge (M+1) \delta \ge F$, and the marking cost bound established for fallback then pays the entire fallback using a second copy of $V_E$. If there is no switch, the second copy is unnecessary. Thus, pathwise,
$$ \mathrm{cost}_{\rm virtual}(E) \le 2 V_E, $$
including a switch on the final raw request or on the final kept request, and including any truncation of an epoch. The expectation in the display for $V_E$ is always applied to a fixed full word.
The comparison between actual and virtual is by first use. Within an epoch, the first time a label is used, both its actual and its virtual position arrive at the same requested point; by the triangle inequality, the actual cost of that first use exceeds the virtual cost by at most $D$, the maximum of the distance between the two entering positions. All subsequent costs of that label agree, until the next virtual reset. Labels never used cost nothing. Therefore
$$ \mathrm{cost}_{\rm actual}(E) \le \mathrm{cost}_{\rm virtual}(E) + kD, $$
which also covers a virtual hit on which the actual chosen label happens to have to move, and it allows repeated actual positions at the entry to an epoch.
The last comparison is between the table's optimum and the whole-word optimum. For each label $j$, keep only its visits at times retained in $w_E$, and shortcut its other visits inside $E$ by direct metric paths; beginning these retained visits from its original epoch-entering point costs no more than its original movement during $E$. Replacing that point by $u_j$ adds at most $D$ to the first retained visit by the triangle inequality; if there is no retained visit, the label costs zero. The resulting $k$ paths constitute a legal labeled service of $w_E$ from $u$, because each path visits the point chosen by the whole-word optimum at every kept time, with the same label. Consequently
$$ \mathrm{OPT}_u(w_E) \le O_E + kD. $$
Combining these four displays yields
$$ \mathbb{E}[\mathrm{cost}_{\rm actual}(E)] \le 2a(O_E + kD) + 2D + kD \le 2 a\, O_E + (2a+2) k D, $$
where the last inequality uses $k \ge 2$. All comparisons involving the entering actual tuple were pathwise and uniform in that tuple; fresh table bits give the same shadow law after any earlier history.
The suffix estimate reads: for every fixed finite word $\sigma$, the routine starting at any deterministic index from an arbitrary actual tuple has expected suffix cost at most
$$ (4a+2)\, \mathrm{OPT}_s(\sigma) + (2a+2) kD, $$
where all parameters $R, F, M, H, a$ are fixed by the instance. The whole-word optimum pays at least $\delta$ inside each completed raw block, regardless of its entering tuple, and the completed blocks are disjoint intervals of request times. Let $N$ be the number of nonempty epochs. The empty-suffix case is trivial; otherwise the first $N-1$ epochs each contain $R$ completed blocks, so
$$ (N-1) R \delta \le \mathrm{OPT}_s(\sigma), \qquad N \le 1 + \mathrm{OPT}_s(\sigma) / (kD), $$
using $R \delta \ge kD$. Also $\sum_E O_E \le \mathrm{OPT}_s(\sigma)$ because the epochs partition the original word into disjoint parts and the whole-word optimum's movement is additive over any partition of time. Summing the per-epoch estimate over epochs therefore yields
$$ \mathbb{E}[\mathrm{cost}_{\rm suffix}] \le 2 a\, \mathrm{OPT}_s(\sigma) + (2a+2) kD\, N \le (4a+2)\, \mathrm{OPT}_s(\sigma) + (2a+2) kD. $$
Only one epoch's fixed charge remains in the bound. A final unfinished epoch may contain arbitrarily many raw requests, since its kept word is still bounded by $H$ and its fallback cost is still bounded by $F$; no table error or restart charge accumulates with the raw request count. That completes the analysis of the suffix routine on any finite rational instance, assuming its table, filters, and parameters are already available.
The suffix routine takes as given the finite table and the parameters of the instance. Obtaining that table requires one long finite computation independent of the request word. Preprocess by storing $n, k, d$ in a fixed canonical encoding and $s$ likewise: integers without leading zeros, rational distances with positive denominators and relatively prime numerators and denominators, matrix entries in fixed index order. Store the actual labeled tuple $s$, initialize a binary request counter to zero, and set a flag indicating that suffix service has not started. This takes polynomially many bit operations in $L$ and produces $O(L)$ bits, since rational reduction is polynomial in the encoding length (in the Euclidean algorithm the larger positive magnitude decreases by at least a factor two in every two remainder steps) and $n, k \le O(L)$.
Fix once and for all a deterministic finite-alphabet bit machine $P$ that on the canonical encoding of $(n, k, d)$ computes $D, \delta, R, F, M, H$, constructs the rational optimum and the dyadic table, and writes a complete output on an initially blank work tape. The output consists of the parameters including $a$ and $b$, an explicit list of table records with each key $(w, r, c)$ and its dyadic numerators in label order, and four unary strings of lengths $H, R, M, b$. If $S$ is the total output length in bits, then $H, R, M, b \le S$ because unary strings of length at most $S$ are included. The output is a consecutively written finite string, so its representation cannot describe a large but empty or heavily compressed table as though the table had already been written. All choices inside $P$ are deterministic: length-then-lexicographic ordering of finite indices, and the fixed Fourier-Motzkin step, the fixed back-substitution step, and the fixed dyadic rounding. Since $\delta > 0$ and the finite flow system is feasible, $P$ halts on every valid input. Let $T_P \ge 1$ denote the finite number of elementary transitions $P$ makes. Neither $C_0$ nor a source policy nor a bound on $T_P$ is an input to $P$; the existence theorem only certifies feasibility of the finite arithmetic that $P$ performs.
The bounded-implementation bound reads: given the explicitly written constructor output of length $S$, the suffix routine can be implemented with a uniform polynomial number of bits of storage and a uniform polynomial number of bit operations per request in $L + S + 2$. These bounds hold for every reachable state and every outcome of the routine's random choices. Each table sample uses exactly $b$ fresh unbiased random bits.
This is a state count. Let $m = L + S + 2$. Since $H, R, M, b \le S$, the numeric values $H, R, M, b$ are at most $m$ and $n, k \le O(m)$. Use explicit lists, binary counters, and bounded-length strings for the following state: the actual and virtual tuples, each of at most $k$ point indices; the kept word of at most $H$ indices; the filter of at most $H$ live entries, each a tuple of at most $k$ indices plus a move counter of at most $M$; the current raw block's set of at most $k+1$ points; a completed-block counter of at most $R$; fallback marks together with their assigned labels, at most $k$ protected points; a mode flag; and the virtual positive-move counter capped at $M+1$. For each raw request, scan every live tuple to determine whether it covers the request. If the request is kept, copy the surviving entries and generate at most $k$ children per removed entry; even materializing all $kH$ temporary children uses only $O(m^4)$ bits for the temporary lists, on top of $O(m^3)$ bits for the live list. At a table decision, locate the record by scanning the output and comparing its key (prefix, request, virtual tuple) with the required one. The filter lemma and the table-mode invariant ensure every requested key has prefix length less than $H$, and the constructor writes a legal row for every reachable key, including keys reachable only after dyadic rounding. Sample with exactly $b$ fresh bits using that row's stored numerators; the sampled label is allowed because disallowed labels have numerator zero. Every access, scan, copy, or cleanup uses polynomially many bounded-length string operations. At the end of the request, discard obsolete lists and temporary strings, carrying only the stated compact state into the next request. No counts of raw epoch length, global epoch number, cumulative movement total, or unfiltered request history are stored. Cleanup is included in the same polynomial bound, and every bound is deterministic and independent of the probability of the current state.
The online schedule proceeds as follows. At request number $t \ge 1$, set $g(t) = \lfloor \log_2(t+1) \rfloor$. Simulate $P$ from scratch on the stored canonical input for at most $g(t)$ elementary transitions. If $P$ has not halted, serve the current request with label $1$. If $P$ has halted, use its output to serve the current request by the suffix routine. At the first successful simulation, initialize a fresh suffix epoch including this request and set the activation flag. At every later success, retain the suffix state from the preceding request and perform its next step; recomputing the identical table does not reset that state, since only the prescribed epoch boundaries do so. Erase the simulation workspace and table after use, preserving the canonical input, actual tuple, request counter, activation flag, and compact suffix state.
The scheduling bound reads: there is one polynomial $p$, independent of the instance, such that preprocessing uses at most $p(L)$ bit operations and serving request $t$ uses at most $p(L + \lceil \log_2(t+1) \rceil)$ bit operations for every reachable history and internal state. Activation occurs at a finite deterministic time $t_*$ depending only on $(n, k, d)$.
The request counter has $O(g(t)+1)$ bits. Incrementing it and determining $g(t)$ cost a polynomial in that length. A simulation lasting at most $g(t)$ elementary transitions uses the copied input and at most $O(g(t)+1)$ additional cells on each of a fixed number of tapes, and explicit simulation, including copying the $O(L)$-bit input, locating tape heads, counting transitions, and erasing the workspace, has polynomial cost in $L + g(t) + 2$. Whenever a simulation succeeds, a fixed finite-alphabet machine has written at most a constant times $g(t)+1$ bits, so $S = O(g(t)+1)$. The bounded implementation lemma then bounds all suffix work by a uniform polynomial in $L + g(t) + 2$. The failure action, updating the actual tuple, and issuing the chosen label have smaller polynomial bounds. The preceding request's budget was no larger than the current one, and the cleanup convention leaves no accumulated workspace depending on the number of earlier requests. Choose absolute constants $A$ and an integer $c$ large enough to cover preprocessing and these finitely many polynomial bounds, and set $p(x) = A(x+2)^c$. Since $g(t) \le \lceil \log_2(t+1) \rceil$, this is the single polynomial $p$ the theorem asserts. The bound is worst case, so it implies the required conditional expected bound at every reachable state.
Define for analysis only
$$ t_* = \min\{t \ge 1 : g(t) \ge T_P\} = 2^{T_P} - 1. $$
It is finite and depends only on $(n, k, d)$, so neither $s$ nor the request word nor irrelevant padding in the rational representation of $d$ can change it. Monotonicity of $g$ ensures every simulation from $t_*$ onward succeeds. The algorithm never computes $T_P$ or $t_*$ in advance; it detects success by the ordinary halting state of its capped simulation.
Proof of Theorem 1. The preprocessing and schedule above define one randomized causal algorithm that uses only unbiased random bits and, at each request, moves exactly one labeled actual server to the requested point. By the scheduling bound, its bit complexity has the required form with a single polynomial $p$.
Fix any finite request word $\sigma$ independent of the random bits. The requests before activation cost at most $(t_*-1) D$ in total, since each moves a single server over distance at most $D$. If $\sigma$ ends before activation, this bound already covers the whole cost. Otherwise, applying the suffix bound from the deterministic start $t_*$, with the whole-word optimum from $s$, gives
$$ \mathbb{E}[\mathrm{cost}_A(\sigma)] \le (4a+2)\, \mathrm{OPT}_s(\sigma) + (t_*-1) D + (2a+2) kD. $$
The same inequality holds for any shorter word, including the empty word, by nonnegativity of its right-hand side.
Since $a \le C_0 \log^2(k+1)$ and $\log(k+1) \ge \log 3$ for $k \ge 2$, set
$$ C = 4 C_0 + 2 / (\log 3)^2, \qquad B_{d,k,s} = (t_*-1) D + (2a+2) kD. $$
Then $4a+2 \le C \log^2(k+1)$, so the movement inequality of Theorem 1 holds with the absolute constant $C$ and the instance-only additive term $B_{d,k,s}$. Repeated positions in $s$ cause no difficulty: the suffix comparison allowed arbitrary actual starting tuples, while the existence theorem and the finite table were used only from the distinct virtual tuple $u$. The polynomial $p$ and the constant $C$ do not depend on the instance, and the algorithm never reads $\sigma$ before serving it: requests arrive one at a time and decisions use only the current request and stored state. That proves Theorem 1.
The construction converts the companion existence theorem into one uniform algorithm on finite rational metrics. The policy the companion theorem promises is never executed or queried; it certifies the feasibility of the finite flow system. A rational solution is computed exactly, and its conditional rows are rounded to dyadic probabilities and sampled with unbiased bits. The deterministic filter keeps a single finite table sufficient for arbitrarily long epochs, without letting the rounding loss grow with raw epoch length. The computational guarantee rests on the permitted dependence on the binary length of the request counter: the constructor's running time $T_P$ determines activation time $2^{T_P} - 1$, and the movement before activation enters the additive constant $B_{d,k,s}$. Those quantities are finite with no size bound asserted. The same ratio with a useful bound on startup movement, or with a uniform per-request bound in $L$ alone, is not obtained by this construction.