========================================================================
RANDOMIZED K-SERVER IN THE PLANE... NO WAIT, IN ANY SPACE AT ALL:
WHY THE BEST GUARANTEE IS ABOUT (LOG K) SQUARED
A friendly, complete tour for a smart high-school reader
========================================================================
by way of explanation of the paper
"Squared-logarithmic randomized k-server on arbitrary metrics"
(the main theorem, the ideas, and the proof architecture)
This document is written so that a curious high-school student can
read it from beginning to end and understand what the paper proves
and how it proves it. Every technical term is defined when it first
appears. Nothing is hand-waved. A short glossary at the end repeats
the notation.
If you know what a set is, what distance means on a number line,
what an average is, what log base 2 means, and what "power of 2"
means, you can read this. You do NOT need to know any graduate
mathematics.
All logarithms in the original paper are natural logarithms (base e).
Changing to base 2 multiplies every log by a fixed number 1/ln 2 and
does not change any "order of growth" statement. Where a reader may
prefer base 2, we say so.
------------------------------------------------------------------------
CONTENTS
------------------------------------------------------------------------
0. A 60-second summary
1. What is the k-server problem?
2. Competitive ratio: how we grade an online strategy
3. Randomness, and the oblivious adversary
4. The history: from k to (2k-1) to log k to log^2 k
5. The main theorem, stated in plain English
6. The big picture: how the proof is built
7. The game board: metrics, servers, costs
8. Lazy simulation: why we can copy a virtual solution
9. Hidden optimal solutions and their shadow (posterior measure)
10. The tree: approximations by hierarchically separated trees
11. The allocation theorem: sharing k units up a tree
12. The pilot potential: a brake for changing partitions
13. Online partitions: heavy balls and chronological rosters
14. Parked mass and moving anchors: paying for reused labels
15. Rounding: from fractional mass to integer servers
16. Transfer: from one law to one policy on any space
17. Assembling the final bound: where each log lives
18. Honest limits: what the paper does NOT claim
19. A one-page glossary
20. A how-to-read-the-paper map
------------------------------------------------------------------------
0. A 60-SECOND SUMMARY
------------------------------------------------------------------------
Imagine k taxi drivers in a city. Customers call in one at a time
and each call must be sent a taxi. You must drive some taxi to the
customer and every meter driven costs you. You do NOT know future
calls. You must decide online.
The k-server problem is the clean mathematical form of this. The
"city" is any metric space (any set with a distance function obeying
the triangle inequality). You have k "servers" at points of that
space. A request arrives at a point of the space, and one server
must visit it, moving any distance. The total distance moved is the
cost.
The paper answers a fundamental question. If an all-knowing referee
had seen the entire request sequence in advance, they could have
planned the cheapest possible set of taxi trips. Call their total
cost OPT. The paper shows:
There is ONE randomized online strategy such that, for ANY metric
space, ANY starting positions of the k servers, and ANY sequence
of requests, the expected cost is at most
C * (1 + log(k+1))^2 * OPT + B,
where C is a fixed absolute number (not depending on the metric,
on k, on the starting positions, on the sequence, or on its
length), and B is a finite number that may depend on the metric,
k, and the starting positions, but not on the requests. If the
starting positions are distinct, B can be taken to be 0.
That is the headline. The rest of this document explains what every
word in that sentence means, why the exponent 2 is correct (it is
the best possible in the worst case; a lower bound of the same
shape is known), and how the proof is built.
------------------------------------------------------------------------
1. WHAT IS THE K-SERVER PROBLEM?
------------------------------------------------------------------------
1.1 Metrics.
A "metric space" is a pair (X, d). Here X is any set of "points" and
d : X x X -> [0, +infinity)
is a function called the "distance" that satisfies three rules, for
every x, y, z in X:
(M1) d(x, y) = 0 if and only if x = y.
(Two different points are at positive distance.)
(M2) d(x, y) = d(y, x).
(Distance does not care which end is which.)
(M3) d(x, z) <= d(x, y) + d(y, z).
(The "triangle inequality": going straight is never more
expensive than going via a detour.)
Examples:
- The real line, d(x, y) = |x - y|.
- The plane with ordinary straight-line distance.
- A graph with edge weights, where distance is the length of the
shortest path between two vertices.
- The "paging metric" with K + 1 points: one special "origin" and
K "slots". The distance between any two different slots is 1;
the distance from a slot to the origin is 1; the origin to itself
is 0. Every pair of distinct points is at distance 1.
(This is called a "uniform metric".)
- The paging metric can also be seen as a "star": the origin is the
center and the K slots are leaves.
The problem works in ANY metric. That is remarkable: the SAME
strategy is proved to work everywhere.
1.2 Servers.
Fix an integer k >= 2. Imagine k identical "servers". Each server
sits at a point of X. So the current "configuration" of the system
is an ordered tuple
s = (s_1, s_2, ..., s_k) with each s_i in X.
The label i runs from 1 to k. Repetitions are allowed: several
servers may stand on the same point.
1.3 Requests and service.
Requests arrive one at a time. A request is a point r_t of X
("the t-th customer is at r_t"). To serve the request, you must
designate one server, say the i-th, and move it from its current
position to r_t. The cost of this move is d(s_i, r_t). All other
servers stay put. If some server is already at r_t, you may serve
the request with it at cost 0 ("lazy" service).
Repeat for t = 1, 2, ..., H, where H is the number of requests.
The total cost of your service is the SUM of all move distances over
the whole sequence.
1.4 Offline optimum.
Suppose you COULD see the future. That is, someone hands you the
whole request sequence r_1, ..., r_H in advance, and you get to
plan every move knowing what will happen. Given the same starting
configuration s, what is the smallest possible total cost?
Call that number OPT(s, r_1, ..., r_H). It is a well-defined
finite number; the minimum is taken over all legal sequences of
choices of which server to move at each step. (There are only k
choices per step, so the number of candidate schedules is finite:
at most k^H.)
OPT is the benchmark. It is the "if you had magic foresight" cost.
No online strategy can beat OPT; the question is how close it can
get without foreknowledge.
1.5 Online strategy.
An "online strategy" (also called an algorithm or policy) must,
at each step t, choose which server to move BEFORE seeing request
t + 1, t + 2, and so on. It knows:
- the current configuration,
- the requests r_1, ..., r_t up to now.
It must be causal: its choice at step t may depend only on the
data available through step t. The future is silent.
The k-server problem is the study of the best online strategies.
1.6 Three classic versions of the problem.
- Paging. X is the "uniform metric" above. A paging system has
K slots of physical memory ("the K servers") and calls for one
of K+1 "pages" (the origin is the special request that some
page is not in memory). Bringing a missing page into memory
costs 1; serving a present page costs 0. Classic.
- Weighted paging. Each page has a "size". Bringing it in costs
its size. Slightly more general.
- Metrical task systems. A broader setting where you also pay a
"service cost" that depends on the current state. The paper
works in the simplest version (only movement costs) and gets
the best known bound there.
- Metrical service systems. Several tasks at once. Out of scope.
The math paper is written entirely in the language of metric spaces
and does not privilege any particular real-world story. But taxis
and paging are exactly what the abstraction is modeling.
------------------------------------------------------------------------
2. COMPETITIVE RATIO: HOW WE GRADE AN ONLINE STRATEGY
------------------------------------------------------------------------
2.1 A single number to compare online to offline.
An online strategy A is called "c-competitive" (with an "additive
term" B) if, for every starting configuration s and every finite
request sequence sigma = (r_1, ..., r_H),
cost_{A, s}(sigma) <= c * OPT(s, sigma) + B.
Read this formula. On the left, what you can actually achieve with
a causal strategy A. On the right, c times what a magic-foresight
referee could achieve, plus a small correction B that is allowed to
depend on the metric, on k, and on the starting configuration, but
NOT on the request sequence or its length.
The smaller c is, the better the strategy. "c" is called the
competitive ratio.
If B can be taken to be 0, the strategy is called "c-competitive
without an additive term" (or "strictly c-competitive").
If c is a function of k, say c = f(k), we say A has competitive
ratio f(k). The whole game is: how slowly can f grow with k?
2.2 Why we care about k at all.
Here's the surprise. On an adversarial sequence of requests, an
online strategy with only k servers cannot possibly match a magic
referee, because the referee can deliver taxis straight to where
customers WILL be while the online strategy keeps driving away from
where customers are about to appear. The competitive ratio measures
exactly how much this foresight gap costs.
Question: is there a function of k that bounds the gap for ALL
metric spaces simultaneously?
Yes. That's the entire point of the field. But finding the exact
slowest-growing such f(k) is the hard part.
2.3 The very first theorem: a lower bound.
Manasse, McGeoch and Sleator (1988 / 1990) proved a clean fact:
For any metric space with MORE THAN k points, no DETERMINISTIC
online strategy is better than k-competitive.
That is: for any deterministic strategy A and any such metric,
there exists a request sequence on which A pays at least k times
the offline cost (for k = 2 this is a factor 2; for k = 100 it is
a factor 100). So deterministically, you cannot do better than k.
This was surprising - can the worst case really be as bad as the
number of servers? And if so, can we do exactly k? Manasse,
McGeoch and Sleator conjectured that k is achievable.
2.4 The "competitive k-server conjecture".
Conjecture (1988). Every metric space admits a deterministic
k-competitive online strategy.
Status: 27 years of work; then Koutsoupias and Papadimitriou (1995)
proved that a specific beautiful strategy works with ratio
(2k - 1) instead of k. And recently (2026 preprint) Coester,
Koutsoupias, Zbysinski announced a k-competitive analysis of
essentially the same algorithm. Either way, the entire deterministic
range is roughly "a constant times k".
So if you want much less than k, determinism is not enough. You
have to flip coins.
2.5 The "competitive ratio of a metric" and the metric's geometry.
The worst-case competitive ratio as we vary the metric is a
geometric property of the metric. For example, the "uniform
metric" (the paging metric) admits randomized ratio exactly the
H_k = 1 + 1/2 + 1/3 + ... + 1/k harmonic number. On the real line,
or on any tree, the situation is dramatically easier.
But the head-line question is: over ALL metric spaces simultaneously,
what is the best function of k?
2.6 "Worst case over every metric".
The paper's theorem is the following kind of statement:
for every metric space (X, d),
for every k,
for every starting tuple s,
there is some randomized online strategy A_{X,k,s}
whose expected cost is at most
C * (1 + log(k+1))^2 * OPT(s, sigma) + B
for every sequence sigma. By "the same strategy works for all
sequences", we mean: ONE strategy A_{X,k,s}, fixed up front, works
for every sequence simultaneously. It does not get to be different
for different problems.
"Expected cost" means: we average over the strategy's internal
coin flips, treating the request sequence as fixed and chosen
independently of those flips (see Section 3).
------------------------------------------------------------------------
3. RANDOMNESS, AND THE OBLIVIOUS ADVERSARY
------------------------------------------------------------------------
3.1 Why coin flips help.
A DETERMINISTIC strategy can be predicted by an adversary: the
adversary sees your strategy's code, knows what you will do, and
picks a request sequence that punishes you. A RANDOMIZED strategy
can be harder to attack because the adversary cannot see your coins
in advance.
But we must be precise about who the adversary is and what they can
observe. This is not a small detail: different "adversary models"
give completely different strengths of result.
3.2 Three adversary models (only one is used here).
- Oblivious adversary. The request sequence is chosen ONCE,
in advance, independent of the strategy's random tape. It may
even depend on the strategy's source code and the starting
configuration, but it may NOT depend on the actual coin flips
the strategy will use. This is the model in which we ask about
"expected cost".
- Adaptive adversary. The adversary chooses each request knowing
the strategy's past random results (but not the next flips).
Stronger than oblivious.
- Adaptive-offline. The adversary is simultaneously playing
against you and against an offline "ghost" who is allowed to
also adapt. The strongest.
The paper uses the OBLIVIOUS model. This matters in every place
where the proof uses "conditional expectation". The math paper
repeats this many times: filtering estimates are made with old
parameters and BEFORE any adaptive choice. This is why.
3.3 Expected competitive ratio.
Say A is a randomized strategy. Its "cost on a fixed sequence
sigma" is a random variable (it depends on the coins). Define:
Expected cost = the probability-weighted average over all the
strategy's coin outcomes.
A is "c-competitive with additive B" if, for every sequence sigma,
E[ cost_{A, s}(sigma) ] <= c * OPT(s, sigma) + B.
For an oblivious adversary, this is the natural and standard notion.
3.4 The paging special case.
For paging (uniform metric on K+1 points with k servers) the problem
is exactly the paging problem: you have k slots in fast memory and
K+1 possible pages.
- Deterministically, the best ratio is exactly k. (Manasse-
McGeoch-Sleator lower bound plus a matching algorithm.)
- Randomized, the best achievable ratio is exactly the harmonic
number
H_k = 1 + 1/2 + 1/3 + ... + 1/k.
This is remarkable and clean.
The upper bound is Fleming, Karp, Luby, McGeoch, Sleator, Young
(1991): a randomized marking algorithm is 2H_k. The exact H_k is
McGeoch and Sleator (1991).
3.5 What is the harmonic number H_k?
A useful fact from calculus: H_k is at most 1 + ln k. More precisely:
ln(k) + 1/k <= H_k <= ln(k) + 1.
So H_k "is logarithmically large in k" and no bigger.
By convention, the paper of interest uses l = 1 + ln(k+1), and
everything is stated in terms of l. So O(log k) really means
O(l).
3.6 The moral.
Randomization can beat k deterministically. For paging it beats k
all the way down to log k. A natural guess is that on EVERY metric,
randomization can attain O(log k). That was the "folklore conjecture"
for about three decades. We will see: it is true that O(log k) works
as a UNIVERSAL LOWER bound (you cannot do better), but it is FALSE
that O(log k) works as an upper bound for every metric. Some
metrics need log^2 k.
------------------------------------------------------------------------
4. THE HISTORY: FROM K TO (2K-1) TO LOG K TO LOG^2 K
------------------------------------------------------------------------
This section is the "who proved what" that motivates the main
theorem. Every fact has a citation in the paper's references at the
end. You can skip to Section 5 if you just want the statement.
4.1 Deterministic era (1988 - 1995).
- 1988, 1990. Manasse, McGeoch, Sleator. Introduced the problem.
Proved the deterministic lower bound k for metrics with > k
points. Conjectured k is achieved.
- 1995. Koutsoupias, Papadimitriou. Proved that the "work
function algorithm" achieves ratio (2k - 1). Stunning result:
one algorithm, all metrics, essentially the same constant for
every metric.
- 2026 (preprint, Sept). Coester, Koutsoupias, Zbysinski.
Announced a k-competitive analysis of the work-function
algorithm. This would prove the original conjecture.
4.2 Randomization: paging is easy (1991).
- 1991. Fleming, Karp, Luby, McGeoch, Sleator, Young. A
harmonic lower bound H_k on uniform metrics, and a randomized
marking algorithm achieving 2 H_k.
- 1991. McGeoch, Sleator. Improved the upper bound to exactly
H_k, matching the lower bound.
So paging is completely solved: exact ratio H_k.
4.3 Weighted paging reaches log k (2012).
- 2012. Bansal, Buchbinder, Naor. Weighted paging in O(log k)
competitive ratio, via a fractional primal-dual algorithm plus
an online rounding. This is exactly the order achieved by the
marking algorithm in the unweighted case, but for a harder
problem.
These paging successes fueled the folklore conjecture: "randomized
k-server should be O(log k) on any metric".
4.4 General-metric upper bounds, polylog (2010 - 2018).
- 2010 (SODA). Bansal, Buchbinder, Naor. First (fractional)
result for general finite metrics after a tree embedding.
- 2015 (JACM). Bansal, Buchbinder, Madry, Naor. The first
POLYLOGARITHMIC upper bound for arbitrary finite metrics. The
bound is
O( (log^2 k) * (log^3 n) * (log log n) ),
where n is the number of points in the finite metric. So this
factors a log(k)-squared piece (good) and many log(n) factors
(not good: not in k alone).
- 2018 (STOC). Bubeck, Cohen, Lee, Lee, Madry. Improved the
bound on "hierarchically separated trees" (HSTs) to
O(log^2 k),
using "multiscale entropic regularization". But on general
n-point metrics, the STATIC embedding reduction only gives
O(log^2 k * log n),
which is not a bound in k alone. The log n factor is the
obstruction.
- 2018 (FOCS). James Lee. Attempted an "evolving, fusible HST"
framework that changes the tree as requests arrive. The
general competitive-ratio claim was WITHDRAWN in 2021 by an
erratum in Section 5.3.2. But the METHOD - "heavy-ball
protection" and "accounting for changing partitions" - is
the conceptual ancestor of the paper we are explaining.
- 2026 (ICALP). Coester and Cosson. Made the HST / finite-metric
bounds POLYNOMIAL TIME, with total number of random bits
independent of the request length. But their general finite
metric ratio retains a log n factor.
4.5 Lower bounds (1994 - 2023).
- 1994 - 2005. Karloff-Rabani-Ravid, Blum-Karloff-Rabani-Saks,
Bartal-Bollobas-Mendel, Bartal-Linial-Mendel-Naor. Developed
metric decomposition / Ramsey methods, weakening randomized
k-server lower bounds upward.
- 2023 (STOC). Bubeck, Coester, Rabani. THE RANDOMIZED
K-SERVER CONJECTURE IS FALSE. Two main results:
(i) Theorem 11 + Proposition 8. There exist metrics with
only (k+1) points requiring competitive ratio
Omega(log^2 k), even allowing a FIXED additive constant.
This is the sharp negative answer to the folklore
conjecture.
(ii) Corollary 20. Universal lower bound Omega(log k) on
EVERY metric with more than k points. (This matches
the paging lower bound and is not contradicted by
(i): (i) says SOME metrics need log^2 k, which is
more than log k; (ii) says no metric can be easier than
log k.)
4.6 What is left? The puzzle of the two logs.
After 2023, the situation is:
- NO metric has a lower bound worse than log^2 k (BCR).
- SOME metric has a lower bound as bad as log^2 k (BCR).
- NO constructed strategy for general metrics achieves the
log^2 k order. The best constructions retain a log n factor
from the static embedding.
The obvious question: can we prove an upper bound of O(log^2 k)
matching the BCR lower bound? On EVERY metric, not just HSTs?
The paper we are explaining proves exactly this.
4.7 The main theorem in one sentence.
On every metric, one randomized online strategy has expected
competitive ratio O((log(k+1))^2), with a finite additive
correction. When starting positions are distinct, no additive
correction is needed.
The additive correction is unavoidable when two of the initial
servers start on the same point, because a "shadow" simulation
(line 8.3) needs to bridge the gap. In every other case, the bound
is exact in every input.
------------------------------------------------------------------------
5. THE MAIN THEOREM, STATED IN PLAIN ENGLISH
------------------------------------------------------------------------
Here is the paper's headline theorem, fully precise.
Theorem (main). There is a fixed absolute constant C < infinity with
this property. For every integer k >= 2, every metric space (X, d)
containing at least k+1 points, and every starting tuple
s = (s_1, ..., s_k) in X^k, there exist:
a randomized online strategy A (one strategy), and
a finite number B >= 0 (an additive correction),
such that for every finite request sequence sigma,
E[ cost_{A, s}(sigma) ]
<= C * (1 + log(k+1))^2 * OPT(s, sigma) + B.
The following important caveats are all part of the theorem's
statement in the paper and are crucial to what the theorem actually
means:
(C1) C is an ABSOLUTE constant. It does not depend on the metric,
on k, on the starting tuple, on the sequence, or on its
length. It is a fixed number that the proof could, in
principle, compute explicitly. It is not small; it is
"like 4 * (2a + 1)" for some a defined in the proof - some
finite astronomical number. The theorem does not try to
make it look tight.
(C2) B may depend on the metric, on k, and on the starting tuple.
It may be huge; it may be infinite in principle for an
infinite metric. But B is a CONSTANT once the metric, k,
and the starting tuple are fixed. It does NOT depend on
the request sequence or on its length. So for very long
sequences B is negligible compared to the OPT term.
(C3) The SAME strategy A works for every finite request sequence
simultaneously. It is not a sequence-by-sequence strategy.
(C4) The SAME strategy A works for every horizon H. There is no
"the strategy is different for different horizons" caveat.
(C5) If the initial servers are at DISTINCT points of X, one can
take B = 0. Then the competitive ratio is C(1+log(k+1))^2
with no additive term at all.
(C6) The metric space may be INFINITE, UNBOUNDED, or both. There
is no finiteness, no compactness, no bounded-diameter
assumption.
(C7) There is NO complexity / efficiency claim. The strategy is
mathematically well-defined. The proof does not claim you
can run it in polynomial time. (Polynomial-time versions
do exist in separate work; Coester and Cosson 2026 is the
relevant reference in the bibliography.)
So the theorem's content, morally, is:
randomization reduces the ratio from "roughly k" (deterministic,
across all metrics) all the way down to "(log k)^2", and no
better is possible in the worst case (BCR 2023 lower bound),
and this is done with ONE strategy on EVERY metric.
The constant of proportionality is fixed once, for all inputs.
That is the sharp order of the problem in the worst case over
metric spaces.
Let us double check what "no better is possible" means. The BCR
lower bound says: there exists a metric on k+1 points forcing any
randomized strategy to pay at least c' * (log k)^2 * OPT for some
absolute c' > 0 (up to a fixed additive term). So the upper bound
ours and the lower bound theirs disagree at most in the absolute
constant. In that sense the theorem is order-tight.
------------------------------------------------------------------------
6. THE BIG PICTURE: HOW THE PROOF IS BUILT
------------------------------------------------------------------------
At the very highest level, the proof has seven steps. Each step is
an idea you could explain to a friend. Each subsequent section fills
in the details. You can read this section first, then read
subsequent sections, and you will always know where you are.
6.1 Step 1: fix a "hidden optimal solution" and watch its shadow.
Idea. Pretend we cannot see the future, but SOMEONE can. Let that
someone choose, for each possible future, the best sequence of
server labels. Treat that chosen sequence as a hidden random
variable "Z" determined by the request sequence. From the revealed
prefix we can compute the CONDITIONAL DISTRIBUTION of Z. That
conditional distribution is called the "posterior".
Think of the posterior as a "shadow" of the hidden optimal solution
projected onto the current observed history. The shadow is what we
can actually see.
This is a standard trick in online algorithms and it is central to
the paper. It converts the online problem into:
"Track the posterior distribution of a hidden optimal solution
online."
The posterior is a probability distribution over configurations of
k labeled servers. It is the thing we want to stay close to.
Now, catching up with a DISTRIBUTION is much harder than catching
up with a POINT. The whole engineering of the paper is about
representing the distribution in a compact, trackable form. This is
where tree embeddings, partitions, and rounding all come in.
6.2 Step 2: reduce the true metric to a fixed tree.
Idea. On a tree, moving servers is easy to analyze. On a general
metric, it is not. Standard theory says: any finite metric can be
approximated by a tree with O(log n) distortion - and if you are
careful and change the tree adaptively, you can hope to keep the
distortion to log k instead of log n.
But the paper does NOT use an approximation of the metric in a naive
way. It uses something subtler. It builds ONE fixed finite object
called a "prefix tree of label strings" whose leaves correspond to
the points of the metric (approximately), and whose edges carry
"semantic" weights.
The point of the tree is that the posterior distribution's "serving"
problem on the tree can be solved and tracked by a fractional
algorithm, and then realized back in the metric.
6.3 Step 3: allocate fractional server mass on the tree.
Idea. On the tree, we want to keep some real-valued "amount of
serving mass" q_v at each vertex v, with these rules:
(i) The root holds q_root = k, exactly.
(ii) The children of any vertex v hold amounts that sum to at
most q_v. (We "spend" all mass going down, or "park" any
leftover at v itself.)
(iii) For every vertex v, q_v is at most a constant times the
posterior expected number of hidden servers in v's
subtree. So mass is dominated by the shadow.
(iv) The leaf of every request in the CURRENT tree holds at
least 1. So the request is always "servable".
If we can maintain such q_v whose CHANGES stay small (sum of
r_{depth} * |change| is O(log k) times the shadow's movement), and
we then round it, we get a strong online algorithm.
This is the content of what the paper calls the "allocation
theorem". It is the hardest single technical component of the
paper. It uses:
- rank coordinates (the probability that a subtree contains fewer
than a hidden servers);
- convex "rank functions" l^beta(p) with parameters tuned to subtree
sizes;
- a "simplex tracker" to make proportions vary slowly;
- a "side tracker" to handle near-dominant children;
- hysteresis to choose between two output rules.
We will explain the conceptual role of each in Section 11.
6.4 Step 4: choose tree partitions that adapt to local mass.
Idea. The tree structure needs to be built from the metric. It
cannot follow the fastest-changing ball-mass ratios at every scale,
because doing so would cost another factor of log. Two structures
solve this:
- "Heavy balls": balls around requests where the mass is very
concentrated. Only ONE change per request per level.
- "Chronological rosters": a small list of balls per level,
chosen by a deterministic age rule, with a random subroster.
Changes cost less on average because of the random retire.
Both structures use the pilot potential (Section 6.5) to PAY for
changes.
The clever bit is that the coefficient on changes is a LOCAL mass
ratio, not a global worst case. When the ball-mass ratio is small
(very concentrated), changes are cheap. When it is large, there are
few such levels (a telescoping "ball-mass" argument controls the
sum). This local-ratio trick is the reason the log-n factor
disappears.
6.5 Step 5: pilot potential - a brake for changes.
Idea. Whenever a partition changes, the allocation q_v will likely
change too. We want to charge those q-changes to something. The
"pilot potential" is a compact variational object that gives a
NUMERICAL potential value small enough that its decreases pay for
the changes, yet large enough that its increases are bounded by
O(log) times the hidden mover's physical cost.
Concretely, at each scale r, define a function L_r(mu, g) of a
measure mu and a function g, as the MINIMUM over certain "vector
of sites" z of a linear functional. Two properties are proved:
- L_r is concave in mu, so filtering (revealing more of the
history) cannot increase it in conditional expectation.
- Its DRIFT (physical movement of the hidden mover at scale r)
is at most O(log k) times the mover's distance, by a local
concentration argument.
The concavity and drift together make L_r a legitimate potential
that can be "spent" on partition edits without paying more than
O(log k) per unit of hidden movement, uniformly in scale.
The "local concentration" step is where the extra log comes from.
When a scale is "concentrated", the integrator's optimal site is
almost AT the request, so moving it is cheap. When a scale is "not
concentrated", the potential is trivially bounded and only a few
such scales exist by the ball-mass telescope.
6.6 Step 6: real-metric rounding and moving representatives.
Idea. The q_v from Step 3 are REAL NUMBERS. We need k INTEGERS on
the tree (one per tree vertex, summing to k) whose values stay
close to q_v in conditional expectation. Also, since the actual
points of X are represented by tree anchors, we must pay whenever a
retained tree vertex's anchor moves to a new nearby anchor.
Both are handled by clean local arguments:
- "Balanced rounding with prescribed random total" gives an
integer n_v with the right mean and with |change| at most 32
times the fractional changes plus 11 times a small dependence
on the parent.
- "Retained-anchor travel" pays moving anchors using a normalized
potential, with a size tracker that resets only when a key's
posterior size drifts by a factor of 6/5.
Both are local: no horizon-dependent factor.
6.7 Step 7: transfer from one law to one policy.
Idea. Steps 1-6 prove the theorem for a FIXED finite metric and a
FIXED finite probability distribution on finite request sequences.
We need to get rid of that.
Three ingredients in the paper:
- "Episode amplification". Cleverly concatenate forward, reversed,
and reset blocks so that the ADDITIVE term gets amortized away
over N episodes. Choose N large enough. This gives a policy
with no additive term on a fixed finite metric, distinct start.
- "Finite separation via Yao". Using the finite minimax theorem,
turn "for every single sequence there exists some strategy" into
"there is ONE strategy for every sequence in a finite family".
- "Tychonoff compactness". Take the product of all decision-point
simplices (one simplex per possible history). The product of
compact simplices is compact. The "for every finite input there
is a policy" constraint defines closed subsets of this product.
Finite-intersection property says ONE policy works for ALL
finite inputs simultaneously.
Together, these remove every dependence on the input law, the
horizon, and the size of the metric. What remains is exactly the
main theorem's statement.
------------------------------------------------------------------------
7. THE BOARD: NOTATION WE WILL USE EVERYWHERE
------------------------------------------------------------------------
Let us line up symbols that recur in every later section of the
paper. Learning them now saves confusion later.
7.1 Configurations.
A "configuration" is a multiset of k points of X, one per labeled
server. That is: a tuple (c_1, ..., c_k). We always allow
repetitions: two servers can be on the same physical point.
7.2 Matching distance between two configurations.
If A = (a_1, ..., a_k) and C = (c_1, ..., c_k) are two
configurations, define their "matching distance":
M(A, C) = min over permutations pi of {1, ..., k}
of sum_{i=1}^k d(a_i, c_{pi(i)}).
Meaning: if we do not care which server has which label, what is the
cheapest way to match each a to a distinct c? M(A, C) is the total
cost of that matching. It ignores labels but respects positions.
Note: M(A, C) is not necessarily d(A, C) - labels sometimes have to
be "renamed". This is crucial for compositions and for lazy
simulation.
7.3 Strong laziness.
A strategy is "strongly lazy" if it does nothing when a server is
already at the request, and otherwise moves EXACTLY ONE server to
the request. Equivalently: it does not move any server except to
serve a request, and it moves only one such server.
7.4 Constants and little ell.
Define the "little ell":
ell = 1 + log(k + 1) (log is natural)
So ell >= 1 for every k >= 2. "Order O(log k)" and "order O(ell)"
are the same order.
7.5 Metric geometry convenience.
Fix a FINITE metric Y with n = |Y| points for the main body of
the argument. It has:
diam(Y) = max_{y, z in Y} d(y, z) ("diameter")
delta = min_{y != z in Y} d(y, z) ("minimum gap")
The minimum gap is positive because Y is finite, so delta > 0.
7.6 Scales (levels).
Fix an absolute "separation" parameter tau >= 2 large enough for
several later requirements. Define r_0 = diam(Y) and
r_j = r_0 * tau^(-j), 1 <= j <= J,
where J is chosen so that 40 r_J < delta. In words: r_0 is the
coarsest scale (about the diameter), each subsequent r_j divides by
tau, and we stop at depth J when the scale is much finer than the
smallest point-to-point gap.
There are J + 1 scales. They divide the "interesting" range of
distances into logarithmic bands.
7.7 The probability law and the horizon.
For most of the paper we work with:
- a fixed finite metric Y of positive diameter,
- a fixed finite horizon H (number of requests),
- a fixed probability law on request sequences of length H.
Everything is conditioned on that law. It is an "input law" on
Y^H. Later, Section 16 removes this law.
7.8 The optimum.
For each realized sequence sigma, choose ONE optimal service
schedule of the k labeled servers. There are finitely many candidate
schedules (k^H of them), so, given sigma, some optimum exists;
resolve ties deterministically. Call the chosen optimum "Z". It has
k components (one per label) at every time.
The conditional distribution of Z given the prefix sigma_{1..t}
is the "posterior". It is a probability measure on configurations.
7.9 Counting measure of the posterior.
Think of the posterior as a random configuration Z. Its "expected
counting measure" mu_t on Y is defined by
mu_t(S) = E[ number of servers in the set S at time t | prefix ]
for every subset S of Y. Equivalently:
mu_t = sum_{labels i = 1}^{k} P(Z_t^i in . | prefix )
Each label contributes one "atom" of a unit of probability at its
position. The total mass of mu_t is exactly k.
This object replaces "the hidden servers" with something we can
actually compute and reason about.
------------------------------------------------------------------------
8. LAZY SIMULATION: A FREE WAY TO COPY A VIRTUAL SOLUTION
------------------------------------------------------------------------
Here is a beautiful elementary lemma that appears implicitly in
Manasse-McGeoch-Sleator and is proved cleanly in the paper. It lets
us run a "virtual" simulated policy and lift its cost to a REAL
policy for the original k-server problem.
Statement (lazy simulation). Let C_0, C_1, ..., C_H be a causal
sequence of configurations, each containing the request r_t at
time t. Let A_0 be any actual starting configuration. There is a
strongly lazy strategy on the actual servers with
cost(A_0; r_1, ..., r_H)
<= M(A_0, C_0) + sum_{t = 1}^H M(C_{t-1}, C_t).
In words: the actual cost is at most the initial matching distance
from A_0 to C_0 PLUS the total "movement" of the simulators
measured by matching distance between consecutive C's.
Why is this true? Here is the proof idea, in detail.
At each step, after seeing C_t (the simulated configuration at
time t, which is a function of the history so far and hence is
available causally), do this:
- Take a minimum matching m_t from the CURRENT actual
configuration A_{t-1} to C_t. This tells us which actual server
"plays the role" of which simulated server.
- If A_{t-1} already covers r_t (some server is at r_t), do not
move anything. Otherwise move the actual server matched to
whichever occurrence of r_t in C_t we choose, and drive it
straight to r_t.
After this step, we get an updated actual configuration A_t that
still contains r_t. Now consider the quantity
"actual cost so far" + M(A_t, C_t).
By an elementary comparison (the server we just moved was matched
to a specific occurrence of r_t in C_t, and after the move the
SAME matching still matches A_t to C_t, so the two distances agree
up to the moved amount), we get the pathwise inequality
cost_t + M(A_t, C_t) <= M(A_{t-1}, C_t).
Now the composition property of minimum matchings:
M(A_{t-1}, C_t) <= M(A_{t-1}, C_{t-1}) + M(C_{t-1}, C_t).
Summing over t and dropping the nonnegative final matching term
gives the lemma.
Why do we need strong laziness? Because of what happens if the
request is ALREADY covered: no move is required, and the matching
data does not accumulate cost. Without laziness, the actual
strategy might be forced to shuffle servers unnecessarily and pick
up extra cost.
Why do we need CAUSALITY? Because C_t must be known at time t, so
the strategy can be run online. If C_t depends on future requests,
we cannot use the lemma to build an online policy - we only get an
offline comparison. The paper uses the lemma in two flavors: for
online policies (needs causality) and for offline comparisons (does
not).
Counting: the initial matching distance M(A_0, C_0) is a one-time
cost. In every application of the lemma in the paper, this is
either zero (C_0 = A_0) or a bounded quantity (for the repeated-
starting-position case at the end).
Reduction to "cost of the simulation". The paper's strategy will
compute simulated configurations C_t satisfying the requirements.
By the lazy simulation lemma, the actual cost on the real servers
is at most the sum of matching distances of the simulators. So
every subsequent budget about "sum_{t} M(C_{t-1}, C_t)" IS a budget
on the real algorithm's cost. Good.
Similarly: the paper sometimes compares two OFFLINE optima
(solution Z vs. solution Z'). Then only the pathwise inequality is
used, not causality. This is fine because offline comparisons are
just for identifying which configuration is cheaper.
------------------------------------------------------------------------
9. THE POSTERIOR SHADOW AND ITS TWO-PART UPDATE
------------------------------------------------------------------------
Recall the setting from Section 7. There is a finite metric Y, a
finite horizon H, a fixed probability law on Y^H, and we have
chosen one optimal hidden labeled service Z of the k servers. mu_t
is the expected counting measure (mass k total).
The strategy of the proof is essentially:
"Maintain an online proxy for mu_t, using only the observed
history up to time t, then convert the proxy into actual
servers."
To do this we need to understand how mu_t changes across a single
step. It changes in two logically different ways, which the paper
insists on separating.
9.1 Filtering (filtration) vs. drift.
Say the request at time t is x = r_t, and we have just observed it.
We used to know the prefix up to time t-1; now we know the prefix
up to time t. That is: F_{t-1} -> F_t. The "filtration" has grown.
For any random variable depending on the past (say, the position
of some hidden server just before time t), its CONDITIONAL LAW
changes from "given F_{t-1}" to "given F_t". We call that change
"filtering" - it is a change of information, not a change of the
underlying random object.
The "drift" is different: after conditioning on the new prefix, the
underlying random variable itself MOVES (because the hidden optimum
actually moved some labeled server at time t). Drift changes the
OBJECT, not just what we know about it.
The paper separates every change of every potential into these two
parts:
L(Z_{t-1} | F_{t-1}) ---[filtering]--> L(Z_{t-1} | F_t)
---[drift]---> L(Z_t | F_t)
Here "L" denotes "probability law of". The first arrow is "what we
know has changed". The second arrow is "the object has changed".
9.2 Why the order matters, and why we never condition on events
that depend on the new information.
Most quantities we will track are AFFINE in the posterior measure.
An affine functional has conditional expected value the SAME
before and after filtering:
E[ affine(Z_{t-1}) | F_t ] = affine( mu^- ) and
E[ affine(Z_{t-1}) | F_{t-1} ] = affine( mu^{old} ),
and, by the tower property of conditional expectations,
E[ affine(Z_{t-1}) | F_{t-1} ]
= E[ E[ affine(Z_{t-1}) | F_t ] | F_{t-1} ].
So an affine functional's expected filtering change is ZERO. Nice.
A concave functional has conditional expected value that does NOT
increase under filtering. (Because E[f(X)|more info] >= f(E[X|less
info]) for concave f, up to the Jensen inequality direction.)
A convex functional has conditional expected value that does not
DECREASE under filtering.
These one-sided differences are exactly what we need: they say
"filtering cannot hurt" (for concave functionals) or "filtering
cannot help" (for convex functionals).
CRUCIAL: all such statements are made with OLD parameters. That
is, we take the OLD definition of the functional (the one from
F_{t-1}-measurable data) and evaluate its conditional expectation
under the new filtration. We do NOT take the new potential and try
to say anything about its expectation relative to the old. And we
do NOT condition on any downstream event (like "did a reset
happen?") that itself depends on the choice made at time t.
Every time the paper uses filtering, it says this explicitly: the
concavity (or affinity) argument is over ALL steps, including
zero-probability-of-reset ones, and only afterwards do we use the
potential-drop credit to pay for specific adaptive events. This is
what makes the bound valid for an OBLIVIOUS adversary.
9.3 The exact measure update.
Here is the payoff. Fix a request x = r_t. The chosen optimum's
k-th move designates a specific labeled server j_t (deterministically
by our tie-breaking). Denote by mu^- the posterior measure on
F_{t-1}-observations after the filter, and mu^+ after the drift to
time t. Let nu be the LAW of the designated server's old position,
conditioned on F_t. This is a probability measure: it puts mass 1
across all possible old positions of the designated mover.
Then:
mu^+ = mu^- - nu + delta_x,
nu <= mu^-, (domination: nu is a submeasure of mu^-)
nu(Y) = 1, (unit mass)
e_x = int_Y d(x, y) dnu(y), (the "expected mover distance")
and:
mu^+ has at least one unit of mass at x, always.
E[mu^- | F_{t-1}] = mu^{old}.
sum over t of E[e_{r_t}] = Q := E[ OPT ],
where Q is the expected offline optimum on the input law.
The last identity is the key economic statement: the sum of "expected
mover distances" telescopes, in expectation, to the expected cost of
the offline optimum. That is: e_x is exactly the per-request offline
cost, and summing it gives the benchmark.
Moral: the "cost" of the hidden optimum, in mol-unit form, is the
sum of the e_x's. Any potential that pays for these e_x's is
implicitly paying for OPT.
9.4 Why "mu^+ has a unit at x" is important.
It says: whatever the conditioning, the posterior "sees" the
request. Later we will demand that our tree allocation and our
rounding both have a "leaf with at least one unit" at x. This is
exactly what lets us assign one simulated server to the request at
every time, which then makes the simulated configurations legal.
9.5 Who cares about the "stationary" part mu^+ - delta_x?
The measure mu^+ has k total mass. It sits at x plus elsewhere. The
"elsewhere" part is what remains at the previously designated
positions after we have pulled one unit into x. That "stationary"
part is exactly (mu^- - nu), which is dominated by mu^+, so no new
mass appears; we can always find it if we look only where mu^+ is
positive.
This is used at the leaf end: the requested leaf gets a unit because
the "elsewhere" mass does not vanish.
9.6 The ball-mass telescope (a tiny but crucial lemma).
One silent workhorse in the proof: a scale sum over logarithms
telescopes because the same measure is used at all scales. Here is
the exact statement.
Fix constants 0 < a < b. Let mu be a nonnegative measure on Y and
c_0 >= 0 an offset. On a consecutive finite range of scales suppose
c <= A_j := c_0 + mu(B(x, a r_j))
<= B_j := c_0 + mu(B(x, b r_j)) <= K,
with c > 0. Let p >= 1 be an integer with tau^p a >= b. Then
sum over j of log( B_j / A_j ) <= p * log(K / c).
Why? Balls are nested: B(x, b r_j) is contained in B(x, a r_{j-p})
because tau^p a >= b. So B_j <= A_{j-p}. Then
log(B_j / A_j) <= log(A_{j-p}/A_j).
Summing this over j gives a "shifted sum of logs": sum_j log A_{j-p}
minus sum_j log A_j. Interior terms cancel. Only p "left edge" terms
and p "right edge" terms survive, each pair contributing at most
log(K/c). So the total is at most p log(K/c).
This is the local-ratio trick. As a reader, notice this one small
lemma is the reason "logarithms telescope" over scales in the
partition construction, avoiding the log-n factor.
Takeaway for the rest of the proof:
every place we compare fine-scale and coarse-scale masses,
this telescope controls the sum with an ell-sized bound.
------------------------------------------------------------------------
10. THE TREE: A FIXED FINITE OBJECT THAT MIMICS THE METRIC
------------------------------------------------------------------------
The next big move in the paper is to replace the true metric Y by a
balanced tree structure. The tree is chosen ONCE, is independent of
the request sequence, and its vertices and edges have fixed
weights. What changes over time is only the assignment of points of
Y to leaves (labels) and the posterior measures on leaves.
10.1 Why a tree at all?
Three reasons:
- Movement on a tree is summable across levels. The "edge entering
a vertex of depth j" has weight r_{j-1} which decreases
geometrically with depth, matching the ball radii.
- A tree's subnetworks are disjoint: they let us decompose the
"how much mass is below this vertex?" question hierarchically.
- Posterior subtree counts are natural on a tree: N_v(t) is just
"the number of hidden servers whose leaf is below v". There
is a clean inequality (superadditivity) linking parent's "rank
distribution" to children's, which is what the allocation
theorem exploits.
10.2 The prefix tree.
Fix alphabets A_1, A_2, ..., A_J. Each A_j is finite. Let T be
the tree whose vertices at depth j are the words w_1 ... w_j of
letters w_i in A_i (including w_j itself). The root is the empty
word (depth 0). Leaves are depth-J words.
Vertex depths are 0, 1, ..., J. The "child" relation is the obvious
one: append one letter. This is a complete (possibly huge but
finite) tree.
10.3 Edge weights.
The edge entering a nonroot vertex v of depth |v| = j has weight
weight of the edge entering v = r_{|v| - 1} = r_{j-1}.
Equivalently: the "top" vertex (depth 0, root) has no incoming edge.
Depth-1 vertices connect to root by edges of weight r_0. Depth-2
vertices connect to depth-1 parent by edges of weight r_1. And so on
down to depth-J leaves with incoming edges of weight r_{J-1}.
10.4 The leaf metric on T.
Define a distance d_T between leaves of T:
d_T(leaf_1, leaf_2) = r_{LCA_depth(leaf_1, leaf_2)}
where LCA_depth is the depth of the lowest common ancestor of the
two leaves. Equivalently: d_T(leaf_1, leaf_2) = r_j when the first
letter at which the two leaves disagree is level j + 1.
This is the "standard HST metric" (Hierarchically Separated Tree):
each level scales down by tau, and the distance between two leaves
is the scale at which they merge.
10.5 How points of Y map to leaves (the labelled map).
At every time t there is an online random map
xi_t : Y -> A_1 x A_2 x ... x A_J
that assigns each point of Y a full word of labels (a leaf of T).
The map is chosen from the revealed prefix; it is independent of
the future request stream (this is a key causality property).
Properties required (Lemma "fixed alphabet" in the paper):
- xi_t is INJECTIVE. Distinct points of Y get distinct leaves at
level J. (Because level-J cells are singletons.)
- Every point with a given current level-j label lies within
20 r_j of a fixed "anchor" for that label. Equivalently: the
level-j cell has an "anchor" point a_{j, lambda} with
d(y, a_{j, lambda}) <= 20 r_j for all y in the cell.
- Cell diameter is at most 40 r_j. (Two points in the same
level-j cell are at distance <= 40 r_j.)
- If the same label survives from step t-1 to step t, the anchor
is either UNCHANGED or was moved by at most 40 r_j via the
heavy-ball reuse (Section 13).
10.6 Labels: how many are there?
A subtle point: Y can be very large, and used labels can be many.
But two constraints make the label sets finite and fixed in advance:
- At each level and each construction, at most n K^2 histories
can appear "active" at once (n = |Y|, K a parameter of the
chronological roster, Section 13).
- A generous pool of size at most 4 n K^2 + 4 per level suffices:
reserve each active label, and choose a fresh label outside the
entire currently active set and the previous step's set.
The pooled labels are FIXED in advance, independent of the metric
size beyond n or of the horizon. This avoids the "the label set
grows with each step" trap that would make the final bounds depend
on horizon.
10.7 The maps' cost.
Define
P := E sum_t sum_{a=1}^k
d_T( xi_{t-1}(X_{t-1}^a), xi_t(X_t^a) )
where X_t^a is the position of the a-th hidden comparator server
at time t. In words: P is the expected total distance moved by the
comparator when we measure its motion on the TREE.
The upshot of Section 13 (the partition construction) will be:
P <= C * ell * Q + D_part,
where D_part is a finite constant independent of the input law and
horizon. In other words, changing the partitions adds only a
logarithmic factor per unit of comparator movement, plus a fixed
initialization cost.
10.8 What "fixed tree" buys us.
Because T is fixed once the metric and the constants are chosen,
subsequent tracking and allocation algorithms run on a FIXED
combinatorial object. The only thing that changes with time is
where the k comparator servers sit in the tree, and how the
online map labels the points of the metric. The rest of the proof
is entirely about the tree.
There is no approximation-theoretic loss from T's distortion in
the final bound. Rough intuition: P (movement on T) is exactly
what the partition construction charges, and every step of the
metric-to-tree passage is compensated by choosing the anchors so
that they never move more than the ball sizes, which is what P
already accounts for.
------------------------------------------------------------------------
11. THE ALLOCATION THEOREM: SHARING K UNITS UP THE TREE
------------------------------------------------------------------------
This is the technical heart of the paper. We solve a self-contained
problem on the fixed tree T. The solution is one of the two
logarithms in the final bound.
11.1 The problem, stated cleanly.
Run the hidden comparator on the tree T. At each time t there are k
labeled hidden servers at k leaves, and one leaf x_t is the request
(every hidden server's tree position is one of the k leaves; the
request is the leaf of the current r_t under xi_t, i.e. the leaf of
the labelled map at time t applied to r_t).
N_v(t) = number of hidden servers at time t whose leaf is in the
subtree rooted at v.
m_v(t) = E[ N_v(t) | F_t ]. These are the "posterior expected
subtree counts".
Subtree counts have these properties, for every t and every
internal vertex v:
m_root(t) = k,
m_v(t) = sum over children i of m_i(t), for every internal v,
0 <= m_v(t) <= k,
at the request leaf x_t: m_{x_t}(t) >= 1,
m_v(t) is affine in the posterior,
sum over t of |m_v(t) - (filtered m_v)(t)| has a controlled sum.
The last line is exactly the "rank drift bound"; Section 11.3
spells it out.
The allocation problem is to produce NONNEGATIVE REAL amounts q_v(t)
satisfying, at every time t:
(A1) q_root(t) = k.
(A2) sum_{i child of v} q_i(t) <= q_v(t) for every internal v.
(A3) q_v(t) <= C_0 * m_v(t) for every v, some absolute C_0.
(A4) q_{x_t}(t) >= 1.
The first condition says all k "serving units" start at the root.
The second says children get at most what the parent provides
(leftover mass "parks" at v itself). The third says the allocation
never exceeds a constant times what the shadow has. The fourth
ensures the request leaf is servable.
Additionally we want the ALLOCATION to move slowly, meaning: define
V := E sum over t, over nonroot vertices v
r_{|v|-1} * | q_v(t) - q_v(t-1) | .
We want V bounded by a small multiple of the comparator's motion on
the tree, plus a fixed initialization constant. Precisely:
(A5) V <= C_1 * ell * P + D_T,
for absolute C_1 and a fixed finite D_T (depending only on the fixed
tree, radii, and k; independent of the input law and horizon).
The theorem claims you can produce such q_v(t) causally, using only
the observed prefix (and the revealed posterior), starting from any
initial allocation (no initial conditions are required).
11.2 Why this is hard.
Consider the naive rule: "Set q_v(t) = m_v(t) at every v." Then
(A1)-(A4) hold (with C_0 = 1). But the movement V is E sum r |Delta
m_v|, and that can be BIG by a factor of the number of levels: the
posterior moves one unit across the entire tree, which cascades into
changes of m_v at EVERY level. That's not what we want. In fact m_v
is not "stable enough": a single unit moving from one leaf to another
changes m_v on the entire path between them, at every scale.
The repair is to introduce "slack". We allow q_v to be strictly less
than m_v (a factor C_0 < infinity above) as long as it exceeds a
LOWER BOUND L_v(t) which is a "rank function" of the posterior.
The lower bound is chosen so that it tracks m_v, but in a way that
changes slowly when m_v changes fast.
11.3 Rank coordinates and their drift.
For each vertex v and each threshold a in {1, 2, ..., k}, define:
p_{va}(t) = Pr( N_v(t) < a | F_t ).
p^-_{va}(t) = Pr( N_v(t-1) < a | F_t ).
Then:
p_{va}(t) is the "posterior probability that v's subtree
contains at most a-1 hidden servers".
p^-_{va}(t) is the "filtered" version: same count, but with the
pre-drift variable.
The tower property gives
E[ p^-_{va}(t) | F_{t-1} ] = p_{va}(t-1).
So the "drift" delta_t p_{va} := p_{va}(t) - p^-_{va}(t) is the
only thing a change of the hidden trajectory contributes to a rank
coordinate at time t. The rest of |p_{va}(t) - p_{va}(t-1)| is a
"filtering change" whose sum is zero in expectation.
The local drift budget E_v at an internal vertex v is
E_v := E sum over t of [ sum_{i child of v} sum_a |delta_t p_{ia}|
+ sum_a |delta_t p_{va}| ] .
The paper proves a clean coupling inequality:
sum over internal vertices v of r_{|v|} E_v <= 6 P.
Here P is the comparator's tree-movement from Section 10.7. The
reason: if one hidden server moves between two leaves whose last
common ancestor is at depth j, its contribution to |delta_t p_{va}|
is one on each of the two paths strictly below depth j. Weighted by
r_{|v|} and summed over such vertices, that telescopes to at most
6 r_j, which is exactly 6 times the comparator movement at that
step. Sum over t and take expectations.
Moral: "rank coordinates in total drift at most 6 times the
comparator's tree movement." This is the coupon we have to spend in
later steps.
11.4 The rank functions l^beta.
For each parameter beta in [3, 3 + epsilon_*] (epsilon_* = 1/100),
the paper constructs a function l^beta : [0, 1] -> [0, 1] with:
(RF1) l^beta is CONVEX and NONINCREASING on [0, 1].
(RF2) l^beta(p) = 1 - beta p on [0, p_*] (p_* = 1/24).
(RF3) l^beta(p) > 0 on [0, s_*) with s_* = 5/8.
(RF4) l^beta(p) = 0 on [s_*, 1].
(RF5) l^beta is AFFINE and NONINCREASING in beta.
(RF6) sqrt(l^beta) has a common absolute Lipschitz constant.
(RF7) If g = -d/dbeta l^beta, then
(1/96) l^beta(p) <= g(p) <= l^beta(p)
on [p_*/4, 1].
There is an EXPLICIT formula:
l^{3+z}(p) =
1 - (3+z) p, 0 <= p <= p_*,
(s_* - p)^2 [ A_* - z (c_*' + d_*' (p - p_*)) ],
p_* <= p <= s_*,
0, s_* <= p <= 1,
with A_* = 18/7, c_*' = 6/49, d_*' = 1152/343. All pieces meet
with matching values and (first) derivatives at p_*.
Two properties make this the right family:
- The pieces are convex quadratics on the middle interval, so
(RF1) holds.
- The parameter beta lets us stretch the function "down" at rate
proportional to beta. The derivative g controls HOW MUCH does
l^beta change when beta changes: it's exactly the slope in
beta. (RF7) says this slope is comparable to l^beta itself,
uniformly.
Also now we have TWO families in play. Two "rank function" objects
per vertex:
L_v^beta := sum_{a=1}^k l^beta(p_{va})
M_v := sum_{a=1}^k l^{siz}(p_{va}),
l^{siz}(p) := (3/4 - p)_+^2 / (3/4)^2,
where l^{siz} is the "size" function (a broader quadratic cutoff).
Note L_v^beta and M_v are both sums of k terms, each in [0, 1],
so both are in [0, k]. Also M_v is essentially a smooth "how mass
distributed" measure at v.
11.5 Superadditivity.
Here is the key structural lemma. For any internal vertex v, its
children i, and its rank function (either family), the following
inequality holds WITHOUT assuming independence between children:
sum_{i child of v} L_i^beta <= L_v^beta,
sum_{i child of v} M_i <= M_v <= m_v.
Why? Two facts:
- Convexity of l^beta and l^{siz}, plus an "increasing hinge"
majorization argument (Karamata's inequality applied to convex
hinges (b - p)_+): the sum of a convex function over child
rank probabilities is at most its value on the parent's rank
probabilities, adjusted by (d - 1)k padding ones for "missing"
children.
- m_v counts "how many servers are below v on average", and
M_v dominates m_v via l^{siz}(p) <= 1 - p (convexity + endpoint
values) and sum_a (1 - p_{va}) = m_v.
So superadditivity says: the "budget" L_v^beta at a parent covers
the sum of the L_i^beta at its children. Good.
11.6 The parameter beta_v.
Define for each vertex the parameter
beta_v = 3 + (c_beta / ell) * log( k / max(M_v, c_*) ).
Here c_beta > 0 is a small absolute constant, c_* = 10^-4. This is
a "size-adapted" rank function parameter: when M_v is small (v's
mass is spread out), beta_v becomes larger (function drops faster);
when M_v is large (v's mass is concentrated), beta_v is closer to 3.
Key facts about beta_v:
beta_v is in [3, 3 + epsilon_*/2].
In terms of the invariant (below),
"L_v^{beta_v} <= L_v^{beta_i}" whenever i is a child of v,
because M_i <= M_v implies beta_i >= beta_v, and l^beta is
decreasing in beta.
Superadditivity plus the "beta_i >= beta_v" fact shows that the
child lower bounds at their own beta_i are consistent with the
parent bound at its beta_v. That's the "compatible lower bounds"
property.
The INVARIANT we will maintain:
(INV) q_v(t) >= L_v^{beta_v(t)} for every v at every t.
Then:
q_root(t) >= L_root^{beta_root} = k (all ranks zero at root,
so L_root^beta = k).
q_{x_t}(t) >= L_{x_t}^{beta_{x_t}} >= 1 (leaf rank zero, so
rank function = 1).
So (A1) and (A4) hold automatically from the invariant and the
initial value q_root = k plus superadditivity. And (A3) requires
q_v <= C_0 m_v; the theorem's choice of C_0 charges that separately
via the M_v <= m_v domination.
11.7 Core vs. noncore ranking.
To make the rank functions move SLOWLY, we need some slack that
does not depend on the exact current value of p_{va}. The paper
introduces a binary classification of ranks:
- Use an "absolute threshold tracker" with threshold p_*/8 on
every rank value. Let the tracked value be the HELD reference;
refresh it only when the ACTUAL rank moves by more than p_*/8.
- A rank is called CORE if its held value is <= p_*/2.
- After an update: a core rank has p <= 5 p_*/8; a noncore rank
has p > 3 p_*/8. A rank with p < p_*/4 is always core.
Effect on the rank function: core ranks lie in the LINEAR part
l^beta(p) = 1 - beta p (affine in p, so affine in the posterior
measure), so they are cheap to track. Noncore ranks are strictly
above p_*/4 and lie in the quadratic middle, where l^beta changes
smoothly with p.
Let, at child i:
n_i = number of current core ranks,
B_i = sum of their current p values,
S = sum_i B_i,
f_i^beta = sum over noncore ranks of l^beta(p_{ia}).
Then:
L_i^beta = n_i - beta B_i + f_i^beta,
n_i + sup_beta f_i^beta <= C M_i for absolute C.
The first identity decomposes the child lower bound into core count
n_i, core sum B_i, and flex f_i^beta. The second bounds the total
by a constant times M_i, using that a core rank contributes at
least a fixed amount to M_i. Consequences:
if M_i <= 10 c_*, then n_i = 0 and L_i^beta = f_i^beta = 0.
if the core flags are held while ranks filter and drift,
B_i <= n_i^{old}.
11.8 Coarse data: sizes, dominant marks, and gaps.
We need to run a small "size tracker" at each child. Track
M_i(t) with tolerance delta_s = 10^-3. Let hat M_i be the tracked
value. Then introduce a_i(t), the "held size":
- INACTIVE (a_i = 0). Turn on when hat M_i >= 5 c_* (set a_i =
hat M_i). Turn off from active when hat M_i <= 2 c_*.
- ACTIVE. While active, hold a_i until factor 1+delta_s
comparison with hat M_i fails; then update a_i := hat M_i.
The result:
0.9 M_i <= a_i <= 1.1 M_i at active children,
M_i >= c_* if active,
M_i >= 10 c_* implies active.
Now pick a DOMINANT child if it exists: the index o such that
a_o >= 0.85 A where A = sum_i a_i (the active total). It is unique.
If no dominant child exists, all active children are "regular".
The complexity: a dominant child makes the algebra awkward because
its "gap" beta_o - beta_v might be small. Introduce these "epoch"
notions. An epoch is a period during which:
- beta^+ (the tracked upper bound on beta_v) is constant,
- the dominant mark is constant,
- the cumulative l1 variation of the held size vector since the
epoch started is at most A_start / 100.
At the start of each epoch we may reorganize; within an epoch the
"shape" of the star stays stable.
Also define:
h_i = 1 + max(0, log(A / a_i)) for regular i,
h_o = u := U / A for dominant o,
U = side total (sum of a_i over non-dominant children),
A = total active size.
These h_i are the "gap weights". The parameter gap lemma shows, for
absolute c_g > 0,
beta_i - beta_v >= (c_g h_i) / ell.
So bigger "mass disparity" h_i gives more room to fit the child's
lower bound under the parent.
11.9 Fine caps.
The static reduction is: figure out how much reduction is needed
to fit the parent. We will remove "excess" = sum_i d_i - q_v from
children via proportion vectors. For that we need caps d_i above the
lower bound but not too loose.
Caps d_i = n_i + b_i, with n_i the core count and b_i a "flex
estimate" chosen so that:
f_i^{beta_i} <= b_i <= f_i^{beta_v} for regular i,
T := f_o^{beta_v} <= b_o <= (1 + epsilon_b / ell) T
for dominant o,
c_D T <= D <= C_D T (D is the coarse
flex estimate),
where D is tracked separately (an old l^3 sum on noncore ranks of
o) and epsilon_b > 0 is a small absolute constant. The caps are
maintained by a relative tracker with tolerance rho / ell on every
rank function value, interpolated in beta.
Bound: |Delta d_i| in total across all children is at most
C ell E_v + fixed, on non-wholesale steps. So the FINE TRACKING
costs a factor ell but no extra potential slope.
Important: the fine tracking is NOT fed back into the potential
slopes. Otherwise we would get an extra ell. Keeping fine caps
out of the proportion potentials is what makes only ONE ell appear
per star (from coarse variation), not two.
11.10 Removing excess: proportions.
At the end of a star's local updates, before knowing the parent's
current q_v, we have caps d_i, core count n_i, core sum B_i, total
S = sum_i B_i, and D (dominant flex estimate). The required
reduction is
R_0 := ( sum_i d_i - q_v )_+ >= 0.
We will remove R_0 in proportions alpha_i:
q_i := d_i - R_0 * alpha_i for all active i.
Feasibility requirement: for each child i, the removed amount plus
the parent's own lower bound must still meet the child lower bound
L_i^{beta_i}. This translates to:
alpha_i >= 0,
sum_i alpha_i = 1,
S alpha_i <= (1 + eta_i) B_i where eta_i := c_t h_i / ell,
c_t > 0 small absolute.
The last inequality is a per-child upper bound. When S = 0, we have
S alpha_i = 0 = B_i at every child, and the constraint is trivial.
We want alpha_i to change SLOWLY when B and S change rapidly. That
is what the simplex tracker is for.
11.11 The simplex tracker (main case).
The simplex tracker produces alpha^t+1 from alpha^t by a global
minimization:
alpha^1 := argmin over alpha in the simplex
{ G^alpha(alpha; B_t) + S_t * ||alpha - alpha^0||_1 }
where the primitive is a sum over coordinates:
g_i^alpha(a; B) := C_alpha * ell *
int_0^a ( S - (1+eta_i) B_i / s )
/ F_i(log(1/s)) ds
for regular i, and
g_o^alpha(a; B) := C_alpha * ell *
int_1^a ( S - (1+eta_o) B_o / s )
/ F_o(log(1/s)) ds
for dominant o.
Here:
F_i(y) = (h_i + y)^2 / h_i for regular i,
F_o(y) = u + H y (1 + y), H = 1 + log(1/u) for dominant o.
Two denominator properties (both proved below):
(a) Each improper integral converges:
int_0^\infty dy / F_i(y) <= 3,
int_0^\infty dy / F_o(y) <= 4,
absolute and uniform in h_i, u.
(b) The weighted sum satisfies
sum_i alpha_i F_i(log(1/alpha_i))
<= C (u + sum_i alpha_i h_i)
with C an absolute constant.
11.11a. Proof of (a): each integral converges.
Regular. Substitute z = h_i + y (so dy = dz):
int_0^\infty dy h_i/(h_i+y)^2 = h_i * int_{h_i}^\infty dz/z^2
= h_i * (1/h_i) = 1.
Dominant. Split at y = 1.
On [0, 1]: u + Hy(1+y) >= u + Hy, so
int_0^1 dy/(u+Hy(1+y)) <= int_0^1 dy/(u+Hy)
= (1/H) log((u+H)/u)
= (1/H) log(1 + H/u).
With u <= 1/4 and H = 1 + log(1/u), H/u <= 4H, so
log(1+H/u) <= log(1+4H) <= 3H, giving <= 3.
On [1, infty]: u + Hy(1+y) >= Hy^2, so
int_1^\infty dy/(u+Hy(1+y)) <= int_1^\infty dy/(Hy^2) = 1/H <= 1.
Total <= 4.
11.11b. Proof of (b): the weighted sum.
Let y_i = log(1/alpha_i), so alpha_i = e^{-y_i}. Coordinates at
alpha_i = 0 contribute nothing (continuous extension).
**Regular terms.** Two cases.
Small (y_i <= 4h_i):
h_i + y_i <= 5h_i, so F_i(y_i) <= 25 h_i,
hence alpha_i F_i(y_i) <= 25 alpha_i h_i.
Tail (y_i > 4h_i):
h_i < y_i/4 and h_i >= 1 (proportion facts), so
(h_i + y_i)^2/h_i <= (5 y_i/4)^2 / 1 = 25 y_i^2/16.
Also y^2 e^{-y/2} <= 3 for all y >= 0 (maximum of 16/e^2 < 3
at y = 4). So
alpha_i F_i(y_i) = e^{-y_i} (25 y_i^2/16)
<= (25/16) * 3 * e^{-y_i/2}
< 5 e^{-h_i}
since y_i/2 > h_i.
Sum the tail: <= 5 sum_{regular} e^{-h_i}. From the proportion
facts (Section 11.9) and h_i >= 1:
- no dominant child: sum_{regular} e^{-h_i} <= C, and
T_alpha := sum_i alpha_i h_i >= sum_i alpha_i = 1.
- one dominant child: sum_{regular} e^{-h_i} <= Cu, and
h_i >= cH on every side, so T_alpha >= cH(1-alpha_o).
If (1-alpha_o) >= c_0 u for a small fixed c_0, the side
contribution pays the tail. Otherwise alpha_o >= 1 - c_0 u
and T_alpha >= alpha_o u >= u/2. Either way the tail is
bounded by C(u + T_alpha).
**Dominant term.** Put g(y) = e^{-y} y(1+y) for y >= 0. It is
continuous on [0, infty], vanishes at both ends, and its maximum
is 4 e^{-2} / sqrt(5)... concretely g attains ~0.84 < 1 at
y = (3+sqrt(5))/2.
alpha_o F_o(y_o) = alpha_o * u + H * g(y_o) <= u + H g(y_o).
Case alpha_o >= 1/2: y_o = log(1/alpha_o) <= log 2, and
y_o <= 2(1 - alpha_o) (true on [0, log 2]).
Also g(y) <= y for 0 <= y <= 1, so g(y_o) <= y_o.
Hence H g(y_o) <= H y_o <= 2 H (1-alpha_o).
Case alpha_o < 1/2: g(y_o) < 1 and T_alpha >= cH/2, so
H g(y_o) < H <= (2/c) T_alpha.
In both cases, alpha_o F_o(y_o) <= C (u + T_alpha).
**Assembling.** Regular small terms are <= 25 T_alpha; regular tail
terms are <= C(u + T_alpha); the dominant term is <= C(u +
T_alpha). Summing: sum_i alpha_i F_i(log(1/alpha_i)) <= C(u +
T_alpha). That is (b).
The lemma says: at a global minimizer alpha^1,
(feasibility) S alpha^1_i <= (1+eta_i) B_i for every child i,
(payment) S ||alpha^1 - alpha^0||_1 <= G^alpha(alpha^0; B)
- G^alpha(alpha^1; B).
11.11c. Proof of (c): feasibility and payment.
**Payment.** The global minimizer alpha^1 has objective no larger
than alpha^0's:
G^alpha(alpha^1) + S ||alpha^1 - alpha^0||_1 <= G^alpha(alpha^0).
Rearranging gives exactly (c-payment). Done.
**Feasibility.** Suppose alpha^1 violates at some child i:
S alpha^1_i > (1+eta_i) B_i.
Then alpha^1_i > 0 and the derivative of the primitive at i is
gamma_i := (C_alpha ell / F_i(log(1/alpha^1_i)))
* (S - (1+eta_i) B_i / alpha^1_i) > 0.
So decreasing alpha_i lowers G^alpha at rate gamma_i per unit.
If some other active j has gamma_j < -2S, transfer epsilon (small)
mass from i to j:
- G^alpha falls by epsilon gamma_i (positive drop),
- G^alpha at j changes by epsilon gamma_j < -2S epsilon,
- L1 penalty rises by at most 2S epsilon.
Net change is at most epsilon (gamma_j - gamma_i + 2S)
< -epsilon gamma_i < 0 (since gamma_i > 0), contradicting global
minimality of alpha^1. So every other active j has gamma_j >= -2S.
Now sum the inequalities gamma_j >= -2S over all positive
coordinates j. For each positive j:
S alpha_j - (1+eta_j) B_j >= -(2S/(C_alpha ell)) alpha_j F_j.
Summing over j with sum alpha_j = 1 and sum B_j = S:
S - sum_j (1+eta_j) B_j >= -(2S/(C_alpha ell)) sum_j alpha_j F_j
>= -(2SC/(C_alpha ell)) (u + T_alpha)
using (b). Since sum_j (1+eta_j) B_j = S + sum_j eta_j B_j:
- sum_j eta_j B_j >= -(2SC/(C_alpha ell)) (u + T_alpha),
i.e.,
sum_j eta_j B_j <= (2SC/(C_alpha ell)) (u + T_alpha).
But eta_j = c_t h_j / ell and h_j >= 1 (proportion facts), so
sum_j eta_j B_j >= (c_t/ell) sum_j B_j = c_t S/ell.
Dividing by S/ell:
c_t <= (2C/C_alpha) (u + T_alpha).
Finally u <= 1 and T_alpha = sum alpha_j h_j <= C_1 ell for a fixed
C_1 (from h_j <= C ell and sum alpha_j = 1). So the right side is at
most (2C/C_alpha)(1 + C_1 ell). We chose C_alpha (Section 11.7, at
the same time as c_t) large enough that this is strictly less than
c_t. Contradiction. So feasibility must hold.
**In words.** Each integrand is set up so that pulling alpha_i below
the feasible region pays at least twice the linear L1 coefficient S
per unit of mass. The denominator F_i keeps the integral finite at
the tail (large y), leaving a fixed margin C_alpha to spare. The
sum comparison above shows the margin can always be chosen to
outweigh the geometry.
The dominant coordinate's denominator F_o(y) = u + H y (1 + y)
handles the near-dominant case. As u -> 0 (dominant child holds
almost all mass), the integral is still bounded by an absolute
constant. The base point 1 is chosen so that changing u is charged
to the side sizes, not the dominant's mass.
11.12 The side tracker (near-dominant case).
Even with the simplex tracker, the simplex-based Rule I has to be
abandoned when the dominant child nearly fills the parent. The
reason: the ratio S / D (child-core total over dominant flex
total) can be so small that the "error" e_o = b_o - f_o^{beta_v}
cannot be paid by simplex proportions. So when S <= 2D, we switch
to Rule II which is a DIFFERENT output rule based on side reductions.
Side vector w: nonnegative entries indexed by side children,
with sum_i w_i <= C_w for fixed absolute C_w. Two feasibility
requirements:
D w_i <= (beta^+ + theta_i) B_i always,
D w_i >= beta^+ B_i - theta_i z_i D if S <= 2D,
where theta_i = c_w h_i / ell and z_i = a_i / (A h_i). And a
"side potential"
G^w(w; B, D) = sum_i g_i^w(w_i; B_i, D),
g_i^w(s; B_i, D) = C'_w * int_0^s
(D s' - (beta^+ + theta_i/2) B_i
+ D theta_i z_i / 2)
/ (theta_i (s' + z_i)) ds'.
The side tracker's minimization is
w^1 := argmin over w in the side domain
{ G^w(w; B, D) + D * ||w - w^0||_1 }.
Lemma: at the minimizer, feasibility holds, and
D ||w^1 - w^0||_1 <= G^w(w^0; B, D) - G^w(w^1; B, D).
The proof is similar to the simplex tracker: any upper violation
makes the potential's derivative positive (so decreasing is
profitable); any lower violation (when S <= 2D) makes the derivative
negative (so increasing is profitable).
11.13 Rule I vs. Rule II (hysteresis).
The output rule:
RULE I. When S >= D/2.
q_i := d_i - R_0 * alpha_i for all i in I.
RULE II. When S <= 2D and there is a dominant child o.
q_i := d_i - D * w_i for i != o,
q_o := min{ d_o, q_v - sum_{i != o} q_i }.
The two ranges overlap (D/2 <= S <= 2D), and the strategy uses
HYSTERESIS: stay on the current rule until it leaves its range.
Switching costs are controlled by a "switch potential":
Psi_v = D if a dominant child exists and we are on Rule I,
S if a dominant child exists and we are on Rule II,
0 otherwise.
The analysis (coupled with the coarse budgets and the ball-mass
telescope) gives a total expected switching cost of at most
C ell E_v + a fixed constant. Same as everything else, no extra log.
11.14 Feasibility.
Combining everything, the outputs q_i are nonnegative, satisfy
L_i^{beta_i} <= q_i <= d_i <= C M_i <= C m_i, and satisfy
sum_i q_i <= q_v (because we removed R_0 from the cap sum, and
each rule removes exactly R_0 or less).
For the requested leaf: its m_v >= 1, and the leaf has exactly
one member with p_{v, 1} = 0, so L_v^{beta_v} >= 1. By the
invariant, q_x >= 1 at the request leaf.
11.15 Assembling the movement bound.
Local star movement:
E sum_t sum_{i child of v} |q_i(t) - q_i(t-1)|
<= C_par E sum_t |q_v(t) - q_v(t-1)| + C ell E_v
+ D_v^{out}.
The parent term at vertex v is NOT part of the "budget" but is
recursively traced up. Multiply both sides by r_{|v|} and sum over
internal vertices. The left side becomes V (the tree allocation
movement). Each nonroot vertex appears once as a child. The
parent-side term contributes weight r_{|v|} per (parent, child) pair,
but total = sum over parents' own r-weighted parent-differences.
Each parent term appears on the right side at depth |v|, so
V <= C_par / tau * V + C ell sum over internal v r_{|v|} E_v
+ D_tree.
Use sum_v r_{|v|} E_v <= 6 P. Choose tau >= max(2, 2 C_par).
Then:
V <= 12 C ell P + 2 D_tree,
which is (A5) with C_1 = 12 C, D_T = 2 D_tree.
Done. Note that this is exactly the ONE ell that comes from the
allocation theorem. Section 13 will give another ell from the
partition construction. Together they form ell^2.
------------------------------------------------------------------------
12. THE PILOT POTENTIAL: A BRAKE FOR CHANGING PARTITIONS
------------------------------------------------------------------------
We now build the second major tool: a potential that pays for
"edits" of the label map and its associated structures. Two dozen
lemmas in the paper rest on this potential. Here is the concept.
12.1 The problem this solves.
The labelled map xi_t (of Section 10) changes over time. Old labels
are dropped, new labels appear, and their anchor points move. Each
of these events can cause the tree allocation q_v (Section 11) to
change too. In the worst case that is unbounded.
We need a potential PHI such that:
(P1) When a label-map update strictly improves the fit to the
posterior, PHI drops by at least some amount proportional
to the "ideal" size of the edit.
(P2) PHI's INCREASES, on physical movement of the comparator,
are bounded by O(log k) times the movement magnitude,
summed over all scales.
Property (P1) makes PHI a "credit line" for edits: decreasing PHI
pays for making good edits. Property (P2) ensures the credit line
grows slowly enough that the total credit spent is bounded by
O(ell) times the comparator's own cost.
Everything rests on a compact variational definition of PHI as a
MINIMUM over "site patterns" z. The minimum makes PHI concave in
the underlying measure, which is what makes filtering free (Section
9.2).
12.2 The "template".
A "template" consists of three numbers:
sigma in (0, 1], R >= 256, L >= 0.
From these, define the scales D_* = 10 R and D_1 = 100 R. These are
"multiples of local radius" where transitions happen.
Also, define three "bump" functions of a nonnegative scalar v
(thought of as distance divided by local radius r):
b(v) = max(0, min(1, 2 - v/sigma)).
Reading: b(v) = 1 for v <= sigma, decreases linearly to 0
at v = 2 sigma, zero beyond. Width ~ 2 sigma. Lipschitz 1/sigma.
a(v) = min(v^2/sigma^2, 1) for 0 <= v <= R,
2 - v/R for R <= v <= 2R,
0 for v >= 2R.
Reading: a(v) rises quadratically from v = 0 to v = sigma,
stays at 1 until v = R, decreases to 0 at v = 2R, zero
beyond. Lipschitz ~ 2/sigma.
G(v) = max(0, min(1, v/D_* - 1)).
Reading: G(v) = 0 for v <= D_*, rises linearly to 1 at
v = 2 D_*, stays at 1 beyond. Lipschitz 1/D_*.
All distances are dimensionless, measured in units of the local
radius r.
12.3 "Sites" and their feasibility constraints.
A "site vector" z is an assignment of nonnegative weights to points
of Y. Write z_s for the weight at s.
The site vector must lie in the feasible set Z_r, defined by:
z_s >= 0 for every s,
sum_s (z_s - G_s(p))_+ <= 1 for every point p in Y,
d(s, s') >= 5 sigma r whenever z_s z_{s'} > 0.
The second condition is the "capacity" one: at any point p, the
LOCAL amount of s-weight (weight above the G cutoff) is at most 1.
The idea is that locally, the total mass "nearby" any point p is at
most 1, so a site pattern can use mass at most 1 in a neighbourhood.
The third condition is "separation": any two sites with positive
weight are at least 5 sigma r apart. This is a structural
assumption that makes the surcharge construction work: the positive
support of the b-bumps at two positive sites is DISJOINT.
12.4 The integrand.
Given a site vector z in Z_r and a function g : Y -> [0, 1] (the
"edit indicator"), define the integrand at p:
F_z^g(p) = (1 + g(p)) * ( 1 - sum_s z_s b_s(p) )
+ 256 * sum_s z_s * (1 + g(s)) * a_s(p).
Here b_s(p) := b(d(s, p)/r), a_s(p) := a(d(s, p)/r), and similarly
for G.
What do the two terms represent?
- The residual term (1 - sum z_s b_s(p)) is "1 minus the amount
of b-mass installed near p". It is at least 0 and at most 1
(from the capacity constraint). This is the amount of "not yet
handled mass" at p.
- The surcharge term 256 * sum z_s (1+g(s)) a_s(p) charges
256 times (1 + g(s)) per unit of s-weight that a_s touches p.
It "punishes" sites that are not exactly at concentrations of
mass: if a site is at distance more than R r from a point with
significant mass, but less than 2R r (so a_s is still positive
there), the surcharge adds cost.
The temptation to help at a concentrated point: a site at a point
s = x with local mass >= 1. Then 1 - sum z_s b_s(x) can be near
zero if z_x is near 1 (b_x(x) = 1). And the surcharge at x from its
own site is 256 * z_x * (1+g(x)) * 1 = 256 z_x (1+g(x)), which is
a fixed penalty per unit weight. So a site pattern near a concentrated
point does improve the residual always, but the surcharge bounds
how much.
12.5 The potential.
Define
L_r(mu, g) := r * min_{z in Z_r} int_Y F_z^g(p) dmu(p).
This is the template's potential at scale r, for a measure mu and a
"g" function. The factor r carries the scale dimension.
Basic facts (Lemma "compactness, concavity, and uniform bounds"):
(L1) The minimum exists. Z_r is a closed subset of a compact
cube [0, 1]^Y, so the objective is continuous on a compact
set.
(L2) L_r is CONCAVE in mu. This is exactly why filtering only
decreases it in expectation. (Do NOT confuse: concavity of
the potential as a function of mu; the feasible set Z_r is
NOT convex, so the argument does NOT use convexity of Z_r.)
(L3) 0 <= L_r(mu, g) <= 2 r mu(Y).
The upper bound is by taking z = 0. The lower bound is
obvious since F >= 0.
(L4) Every feasible integrand satisfies
0 <= F_z^g <= 514, r Lip(F_z^g) <= L + 1026/sigma.
The "514" comes from (1 + 1) + 256 + 256, but with constants
stripped it is 514 = 2 + 512.
(L5) The positive support of the b_s's at two distinct positive
sites is DISJOINT. (Follows from the separation condition.)
The 514 is a big constant. It is not small, but "a fixed absolute
constant" is all the argument needs. It reappears everywhere.
12.6 The local structure lemma.
The crucial property of L_r is that, at a concentrated request, it
has a "near site" and a small positive slope. The paper states this
cleanly. Let me recast it as a story.
Fix a request x, a template, and small constants
gamma <= min{sigma/64, 1/(1+L)}, delta <= 1/4112.
These are "concentration" thresholds. Let mu be a nonnegative
measure, M := mu(B(x, gamma r)) > 0 the mass in a small inner ball
around x. Define:
h = mu(B(x, D_1 r) \ B(x, gamma r)) / M
"shell ratio": how much more mass sits in the annulus between
the small inner ball and the wider D_1 r ball. If h = 0, all
mass is concentrated in the inner ball. If h >= 1, the
concentration is not strong.
t = (1/M) * int_B(x, gamma r) d(x, p)/r dmu(p)
"inner moment": the average distance to x (normalized by r)
of the inner ball's mass. If t = 0, all inner mass sits at x.
Both h and t are nonnegative and can be small without any of them
being zero.
Lemma (local structure). If h <= delta, and z is any minimizer of
the potential at scale r, then:
(A) Any site s with sigma r/4 <= d(s, x) <= R r/2 has z_s = 0.
(Sites strictly in the middle distance shell are excluded.)
(B) There is a UNIQUE positive site s with d(s, x) < sigma r/4.
Its weight z_s and normalized displacement w = d(s, x)/r
satisfy
z_s >= 3/4,
1 - z_s <= (512 gamma / sigma^2) t + 514 h,
w <= (5 + L) (h + t).
(C) If d(x, y) < sigma r/8, then the "positive slope" bound
[F_z^g(x) - F_z^g(y)]_+ <= C_loc (h+t) d(x,y)/r
holds, where C_loc is an explicit absolute constant like
(L + 1024/sigma)(514 + 8/sigma) + 1024(5+L)/sigma^2.
Roughly, at a concentrated point, the integrand can only
change by O(h+t) per unit of distance.
Rough conceptual proof:
(A) A site in the middle shell would have a_s ~ 1 on the whole
inner ball (distance at least sigma/4 from a centre where the
a bump would peak, still well within a's heavy-support
region). So it would pay surcharge of about 256 * mu(inner)
but save the residual of at most 2 * mu(inner). Net cost
positive => cannot beat z = 0 on that coefficient.
(B) If we wiped the ball B(x, 5 D_* r) and placed a unit site
at x, then the mass in the inner ball (mass M) would witness:
old integrand >= 1 - Znew (because the old sites are all
outside, so residual there is 1 minus the one near-site
weight which is at most Znew). New integrand <= 512 t^2/sigma^2
there. Bounding the rest gives the weight deficit.
(C) Once you have (B), you move the near site from s to x by
paying relocation cost: the b bump is 1 at both, the a bump
moves from u^2/sigma^2 to v^2/sigma^2, surcharge change is
controlled by |w^2 - u^2| <= 2w|w-u|, applied pointwise. The
resulting positive-part bound is exactly C_loc(h+t) * d(x,y)/r.
12.7 The drift bound.
This is the potential's key feature. At each scale r_j, we have a
g-function g_j (fixed for the step) and a measure update
mu^- -> mu^+ = mu^- - nu + delta_x. We want:
sum over j of [ L_{r_j}(mu^+, g_j) - L_{r_j}(mu^-, g_j) ]_+
<= C_dr * ell * e_x.
Where e_x = int d(x,y) dnu(y) is the expected mover distance.
Sketch of the proof:
- For each scale, evaluate the new minimum at the OLD minimizer
z^(j). Then
L_{r_j}(mu^+, g_j) - L_{r_j}(mu^-, g_j)
<= r_j * int (F_j(x) - F_j(y)) dnu(y).
(Because the minimum at mu^+ is at most its value at z^(j),
and by linearity the difference is the integral of the difference.)
Take the positive part.
- At "small" scales, use F <= 514 always:
r_j < 2 e_x / gamma => contribution <= 514 * sum r_j,
which sums to ~ (2056/gamma) e_x.
- At "large" scales, use inner mass >= 1/2:
M_j := mu^-(B(x, gamma r_j)) >= nu(B(x, gamma r_j)) >= 1 - e_x/(gamma r_j) >= 1/2.
Then Lemma pilot-local applies: either the scale is "good"
(h_j <= delta), in which case C_loc*(h_j + t_j) is small at
nearby points; or it is "bad" (h_j > delta), in which case only
Lambda e_x is paid at that scale.
- Sum over good scales uses TWO telescopes:
sum_j min{1, h_j} <= (p_0/log 2) log(2k) (ball-mass telescope)
sum_j t_j <= 2 gamma (1 + log(2k)) (moment telescope)
Both give ell-sized sums.
- Sum over bad scales: number of bad scales is
<= p_0 log(2 k) / (delta log 2) = O(ell).
Each bad scale contributes at most Lambda e_x. So total bad
contribution is O(ell) * e_x.
- Sum over far scales (where d(x,y) >= sigma r_j/8) can be
bounded geometrically: sum over such r_j of 514 r_j <=
(8224/sigma) d(x,y). Integrating against nu gives
(8224/sigma) e_x.
Combined:
C_dr = 2056/gamma + 8224/sigma + 2 Lambda p_0/(delta log 2)
+ 2 C_loc (p_0/log 2 + 2 gamma).
The headline: sum over ALL J scales of the positive drift is
O(ell) * e_x. No log(J) factor. The number of levels NEVER
appears. That is the beauty of the local concentration argument.
12.8 The telescoping corollary.
Here is how you actually USE the potential. Consider a family of
templates indexed by some alpha, each with a nonnegative "weight"
omega_alpha. Assumption:
A := sum_alpha omega_alpha < infinity,
B := sum_alpha omega_alpha C_dr_alpha < infinity.
At each time step:
1. Reveal the new request. Do FILTERING with the OLD g-functions
(one per template). By concavity, the expected total potential
does NOT increase.
2. DRIFT to the new posterior. By the drift bound, the total
potential increases by at most B * ell * e_x.
3. EDIT: update the label maps and their associated g-functions.
Suppose the total potential DROPS by at least a charge c_t
(where c_t = 0 on steps without an edit).
Then:
E sum over all t of c_t
<= B * ell * Q + sum_alpha 0.5 * (initial potential)
and the trailing term is <= 2 k A sum_j r_j = O(k A r_0 / (tau-1)).
Two important sub-points:
- Filtering is summed over ALL steps, before any conditional
selection of edits. This is why we can bound expectation of
c_t unconditionally: no event-dependent conditioning.
- The COUNTABLY INFINITE index set alpha is allowed (for
example, alpha ranging over all tiers h = 1, 2, 4, ...), as
long as the weights are summable and the drift constants are
summable. This is essential for handling infinitely many tiers
with a fixed bound.
12.9 Paying for an edit specifically.
To apply this in a concrete structure, one checks the EDIT HYPOTHESIS:
L_r(mu^+, g_old) - L_r(mu^+, g_new) >= (desired charge).
The paper uses the trick: if z is the OLD minimizer at the NEW
measure mu^+, then
L_r(mu^+, g_old) - L_r(mu^+, g_new)
>= r * int (F_z^{g_old} - F_z^{g_new}) dmu^+.
So we just need to LOWER-BOUND how much the old z "improves" when
we pass from g_old to g_new. Which is exactly what the concrete
edit structures show.
12.10 Why the local structure lemma matters.
You might wonder what forces the potential to have SMALL drift
rather than paying 514 * e_x per scale. The answer: at good
scales (small shell ratio h and small inner moment t), the near
site sits very close to the request. Moving the request by d(x,y)
moves the near site by at most d(x,y), which costs at most
O(h+t) d(x,y)/r per unit of scaling factor r, and after multiplying
by r the drift is O(h+t) * d(x,y).
The sum over good scales of O(h+t) d(x,y) is O(ell) d(x,y) by the
two telescopes.
At bad scales we pay O(ell) e_x once, and the number of bad scales
is O(ell).
Everything telescopes neatly. That's the whole point.
------------------------------------------------------------------------
13. ONLINE PARTITIONS: HEAVY BALLS AND CHRONOLOGICAL ROSTERS
------------------------------------------------------------------------
Fix the pilot template with concrete constants. We will use TWO
templates in this section: a "heavy" template (coarse sub-structure)
and a "tier" template (fine sub-structure). The drift corollary
of Section 12.8 is applied to each template separately, giving
each template its own absolute drift constant C_dr.
The goal of Section 13 is to construct the labelled maps
xi_t : Y -> (A_1 x ... x A_J) and prove:
P <= C ell Q + D_part,
where P is the tree-comparator movement. Recall from Section 10.7
that P is E sum_t sum_a d_T(xi_{t-1}(X_{t-1}^a), xi_t(X_t^a)).
13.1 The structures, top-down.
The full map xi_t is built by stacking THREE sub-structures at each
level j, with precedence from top to bottom:
1. HEAVY STRUCTURE. A set H_t^j of "heavy balls" at level j.
Any point in a heavy ball gets that ball's label.
2. TIER STRUCTURE. For each tier h in {1, 2, 4, ..., 2^b}, a
set of ball centers with radii from [r_j, 2 r_j], with
retirement lifetimes. A point not in any heavy ball gets the
label of its earliest-present covering tier ball.
3. SINGLETON. If neither covers the point, the point gets a
singleton label.
Heavy has precedence over every tier. A tier with smaller h has
precedence over a tier with larger h. This is the "when in doubt,
small h is more important" priority.
Both structures use the LOCAL posterior mass mu^+ at the request x.
They are driven only by qualification conditions and chronological
age. They never inspect the request stream's future.
13.2 Heavy structure.
Fix the heavy template: sigma = 1, R = 512, L = 1, so D_H = D_1 =
100 R = 51200. Choose gamma_H in (0, 1/100) and delta_H in
(0, 1/100) sufficiently small to satisfy the local structure lemma
concentration requirements.
A request x at scale r is called HEAVY at scale r if
mu^+(B(x, D_H r)) <= (1 + delta_H) mu^+(B(x, gamma_H r)).
Intuition: the mass in a small ball around x captures almost all
mass in a much bigger ball around x. So the mass is very
concentrated at x.
At every step, process the following. The current request x is at
some scale r = r_j.
1. If x is heavy AND the current heavy-center set H has no center
within 8 r of x: remove all centers within 100 r of x, then
insert x. The new center gets a fresh independent random
radius U ~ Uniform[16 r, 20 r], held until eventual removal.
2. If x is heavy AND some center is already within 8 r of x: do
not insert.
3. If x is not heavy: do not look at the heavy structure.
The invariant: heavy centers are pairwise at distance > 100 r.
(An insertion removes all within 100 r, and new one is at distance
> 8 r > 100 r - 16 r from any neighbor after insertion.)
For each level j, define the g-function that will be used in the
pilot potential:
g_Hj(p) = rho_H( d(p, H_j) / r_j ),
where rho_H is a clamped ramp increasing from 0 to 1 on [3, 4]. It
detects centers within 3 r to 4 r. At a heavy update, the potential
drop is at least 127 r mu^+(E_x(r)), where E_x(r) is the annulus
(3 r, 120 r] around x. That pays for the update. So the total
EXPECTED edit cost for heavy updates at level j is bounded by
C ell Q + D_H'.
13.3 Roster structure.
For each level j and each tier h in H_k = {1, 2, 4, ..., 2^b},
maintain a chronological roster: a growing list of insertion events.
Each entry has:
- A center c (where it was inserted).
- An AGE (number of subsequent insertions of the same level-tier
whose center is within 20 r of c).
- A LIFETIME (random, described below).
- A RADIUS V drawn from [r, 2 r] with a specific density.
Set K_h = ceil(e^{C_K h}) for an absolute constant C_K chosen
large enough that, for every h >= 1, the two inequalities
e^{-K_h / 2} <= (c/2) e^{-h} and e^{-K_h} <= (c/2) e^{-2h}
hold simultaneously, where c > 0 is a fixed small absolute
constant. The point is that tier-h retirement probabilities
fall off fast enough in h that the two telescoping payments of
Section 13.5 work uniformly over every h.
A request x QUALIFIES in tier h at level j if
mu^+(B(x, D_L r_j)) <= e^h mu^+(B(x, gamma_L r_j)),
where gamma_L < 1/100 is small (and D_L = 100 R = 400 D_H tier
template constants). Higher h means WEAKER concentration threshold
(more permissive). Tier 2^b (the last) always qualifies.
INSERTION RULE. Insert x into tier h at level j if x qualifies
and there is no existing entry of CURRENT AGE < K_h within r/2
of x. If there is such an entry, do nothing (the "parent" already
handles that neighbourhood).
Note: age is measured purely CHRONOLOGICALLY (by counting later
insertions), not randomly. It is deterministic given the request
stream and the insertion schedule.
RETIREMENT. An entry is DETERMINISTICALLY PRESENT at ages 0, 1,
..., K_h - 1. At each subsequent age K_h, K_h + 1, ..., K_h^2 - 1,
the entry RETIRES with fresh independent probability 1/K_h. At age
K_h^2 it RETIRES COMPULSORILY.
RADIUS. Each entry draws V from [r, 2 r] with density
f(v) = (lambda / r) * e^{-lambda (v/r - 1)} / (1 - e^{-lambda}), r <= v <= 2 r,
where lambda = log(1 + K_h^2). (This is roughly an exponential tilted
toward r, with tail scale r / lambda.) All draws independent.
THE KEY: because the insertion rule depends only on AGES (not on
whether prior entries have retired), the insertion schedule is
DETERMINISTIC given the request stream, and radii are independent.
This is what makes the probability arguments in Section 13.4 work.
13.4 The first-hit lemma.
Now comes the probability estimate we need for separation. Fix a
level j, a tier h, and two points x, y with d(x, y) = d << r.
Consider the earliest present covering ball of either point in the
tier's roster. Let
BAD = "the earliest present ball covers one of x, y but not
the other"
(In other words, it SEPARATES x and y.)
Then: Pr(BAD) <= C h d / r.
Where C is a fixed absolute constant and expectations are over the
STRICTLY INDEPENDENT random radii.
The proof is elegant: for a fixed center c with distances
a = min{ d(c, x), d(c, y) }
and given that a single present ball is "first", the two
distances differ by at most d. The ball separates x from y
only if V lies in a small window of width d, which under the
density f has probability at most
(2 lambda d / r) * (p_a + 1/(e^lambda - 1))
where p_a is the tail probability Pr(V >= a). Multiply by the
probability that all earlier balls MISS both points, sum over
the possible candidates (at most K_h^2 of them, by Lemma roster-
count), and use sum_i q_i p_{a_i} <= 1 (probability that SOME
higher ball hits one of the points is at most 1).
The total is at most 2 lambda d / r. And lambda = log(1 + K_h^2) is
at most C h (since C_K is fixed). So Pr(BAD) <= C h d / r.
13.5 The two telescopes for the rosters.
The map xi_t resolves a point by looking at heavy structures first,
then at the earliest covering tier ball. Two "cost" quantities must
be bounded.
(i) PHYSICAL MOVEMENT. Fix two points x, y at distance d << r_j
and let "SEP_j" be the event that the two points' level-j
keys disagree. Whenever this happens, the level-j key of the
current comparator mover disagrees between two successive
states, and we pay r_j for that disagreement under the
tree-metric sandwich (Section 10).
Heavy center first. At level j, a heavy center can produce a
separating radius only if it lies within 20 r_j of x or y:
the possible centers lie in a set of diameter at most
40 r_j + d < 41 r_j, so at most one such center exists. Its
uniform radius in [16 r_j, 20 r_j] then separates x from y
with probability at most d / (4 r_j). Heavy structures thus
contribute at most C d / r_j.
Tier balls. For each tier h <= h_*(j) (the first qualifying
level), the first-hit lemma gives probability at most
C h d / r_j that a tier-h ball fires at one of the two points
but not the other. Tiers h > h_*(j) never fire (the first
qualifying lower tier covers).
Summing over dyadic tiers h in {1, 2, 4, ..., 2^b} with
h <= h_*(j):
Pr(tier part separates x, y) <= (C d / r_j) sum_{h<=h_*} h.
The tier steps are dyadic, so sum_{h<=h_*} h <= 2 h_*.
Since h_*(j) is the first dyadic at least
L_j(x) := log( mu^+(B(x, D_L r_j)) / mu^+(B(x, gamma_L r_j)) ),
we have h_*(j) <= 2 max(1, L_j(x)). Consequently
Pr(SEP_j) <= (C d / r_j) (1 + L_j(x)).
Summing over levels, the additive parts contribute only at
the nonheavy levels, of which there are at most C ell (the
second display of 13.1). The L_j(x) parts telescope:
sum_{j=1}^J L_j(x) <= p_L log k <= C ell
by the ball-mass telescope (Section 9.6), applied at every
level to the two nested balls B(x, gamma_L r_j) and
B(x, D_L r_j).
Multiplying by r_j, summing over j, and evaluating at the
comparator mover x = x_t with its old position y = y_t:
E sum_t sum_j r_j * 1{SEP_j at t} <= C ell * e_{x_t},
where e_{x_t} is the expected mover distance (Section 9.3).
Summing over t: the "physical" contribution to P is at most
C ell Q.
(ii) INSERTIONS. Each insertion into tier h at level j costs
O(r_j / K_h) times its "W mass" (see next) and we want to
sum these. The "W mass" is defined as
W_{t,j,h} = mu^+(B(x, D_L r_j)) if nonheavy,
mu^+(annulus gamma_H r_j < d(p,x) <= D_H r_j) if heavy.
So the insertion charge is r_j * W_{t,j,h} / K_h. Bounding
sum over insertions of this by C ell Q + fixed is what the
auxiliary short roster below is for.
13.6 Short roster - paid by the pilot potential.
The insertion charges are paid as follows. For each level j and
tier h, we build an "auxiliary" roster with the SAME deterministic
insertion schedule but different random lifetimes:
- An entry is present at age 0.
- At each subsequent age increment up to age K_h, it retires
with fresh probability 1 / sqrt(K_h).
- At age K_h it retires compulsorily.
The auxiliary roster's function is
g(p) = E_auxiliary [ rho_L( d(p, S) / r ) ],
where rho_L is a clamped ramp on [1/8, 1/4] and S is the current
set of surviving auxiliary centers. This is the EXPECTED version of
a ramp. Note: the auxiliary roster's g function is DETERMINISTIC
given the request stream, because the auxiliary lifetimes are
averaged out.
BOUND on retirement effect: at any p, an increase in g can only
happen if the old nearest auxiliary center retires. Retirement
probability per age increment is at most 1/sqrt(K_h), and the
number of possible compulsory retirements over a neighbourhood is
at most K_h (by the roster count lemma). So
Pr(old nearest retires) <= K_h^{-1/2} + K_h (1 - K_h^{-1/2})^{K_h - 1}
<= C / sqrt(K_h).
Positive support of g-changes is contained in
B(x, 21 r) \ B(x, r/8) - within the shell.
AT INSERTION: the positive change of g at x is 1 (it was 1 before
the insertion in the ball B(x, r/8), and the new entry covers x at
any radius in [r, 2r], making g(x) = 0). So the g function "drops"
at x during the insertion. That drop drives the pilot potential's
decrease.
Let z be the OLD minimizer of the pilot potential at the new
measure mu^+. The pilot drop when we edit g_old -> g_new is at
least r * int (F_z^{g_old} - F_z^{g_new}) dmu^+. The paper
estimates this from below as (c e^{-h} - C/sqrt(K_h)) r W.
With K_h = ceil(e^{C_K h}) and C_K large enough, the C/sqrt(K_h)
error is absorbed by the c e^{-h} leading term The final inequality:
r W / K_h <= e^{-h} * (pilot potential drop).
So the pilot potential provides at least r W / K_h of drop per
insertion. By Corollary 12.8 (with weights e^{-h} on all tiers,
which are summable), this gives
E sum over all insertions of r_j W_{t,j,h} / K_h
<= (weighted template drift) ell Q + fixed
= C ell Q + D_ins.
13.7 Two structures combined.
The two structures (heavy balls, chronological rosters) supply
three separate expected budgets, each with exactly one factor of
ell and a finite uniform remainder:
(a) Heavy-edit budget (Section 13.2, heavy-edits lemma):
E sum_{t,j: heavy update at t} r_j mu^+(E_{x_t}(r_j))
<= C ell Q + D_H.
(b) Roster-edit budget (Section 13.6, tier-edits lemma, paid
by the auxiliary short roster through the pilot potential):
E sum_{t,j,h: insertion at t into tier h of level j}
r_j W_{t,j,h} / K_h
<= C ell Q + D_ins.
(c) Physical-motion budget (Section 13.5 (i), the separation
estimate for the comparator mover and the physical-witness
motion; see also Section 13.5 (ii) for the retention
bookkeeping that lets stationary members net to zero):
E sum_{t,j} r_j * 1{level-j key of mover disagrees}
<= C ell Q + D_phys.
The constant C in each display is absolute (absorbing tau, D_L,
D_H, gamma_L, gamma_H, C_K, and the tier windows). The remainders
D_H, D_ins, D_phys are finite and uniform: they depend only on
the fixed metric Y, the server count k, the scales, and the fixed
label pools, but never on the input law or its horizon. This
uniformity is the same accounting that Section 15.10 performs for
the rounding tree-movement budget, and is what allows Section 16
to remove the additive term by episode amplification.
Summing (a), (b), (c) and renaming the total coefficient as a
single larger absolute C_P:
P <= C_P ell Q + D_part,
D_part := D_H + D_ins + D_phys < infty.
This is the statement fed into Section 11 (the "embedded cost"
proposition). The partition construction contributes exactly ONE
factor of ell over the offline optimum Q, plus a fixed
initialization term. Section 11 contributes the second ell.
Their product is the ell^2 promised by the main theorem.
The "log number of levels" trap is avoided by the ball-mass
telescope (Section 9.6), not by naive accumulation: the level
sums sum_j L_j(x) <= p_L log k <= C ell are exactly what bounds
the per-level coefficient sum, not a factor of height times a
worst-case log.
------------------------------------------------------------------------
14. PARKED MASS AND MOVING ANCHORS: PAYING FOR REUSED LABELS
------------------------------------------------------------------------
The allocation theorem gives us real masses q_v on tree vertices.
Section 15 will round to integers. Before that, we need to solve a
DIFFERENT problem: the masses are represented in the true metric by
ANCHORS (one anchor per active tree vertex). When a tree vertex
retains its label from step to step but its anchor moves - because
of heavy-ball reuse - the "parked mass" at that vertex must be
"carried" to the new anchor. We must pay for that.
14.1 Parked mass.
Recall the allocation: q_v is the mass at vertex v, with
q_root = k and sum_children q_i <= q_v. The "parked mass" at v:
p_{t,v}^circ := q_{t,v} - sum_{i child of v} q_{t,i}.
The mass that is "redistributed to children's subtrees" plus the
"parked at v itself" equals q_v. At leaves there are no children,
so p_{t,leaf}^circ = q_{t,leaf}. The whole subtree sums to q_v:
sum over w descendant of v of p_{t,w}^circ = q_{t,v},
sum over all v of p_{t,v}^circ = k.
14.2 Variation of parked masses.
By taking differences and using the triangle inequality (a short
computation), one gets
sum_v r_{|v|} |Delta p_v^circ| <= (1 + 1/tau) V,
where V is E sum_t sum_{v != root} r_{|v|-1} |Delta q_v|. So if
the q_v's move by V, the parked masses move by at most (1+1/tau) V.
No extra factor.
14.3 Validity witnesses.
If q_{t,v} > 0, then p_{t,v'}^circ > 0 for some descendant v' of v.
In particular, some point of Y has a leaf below v (so its complete
word has prefix v). Call such a point a "witness". Also, by the
fixed-alphabet property (Section 10.5), every witness for v is
within 20 r_{|v|} of v's last key's anchor.
14.4 Anchor travel cost.
We need to pay for anchor MOVEMENT when a retaining key survives
but its anchor changes. Precisely, per fixed heavy label slot
lambda at level j, define:
b_{t,j,lambda} = sum over depth-j vertices v whose last key
is lambda of p_{t,v}^circ.
M_{t,j,lambda} = mu_t(C_{t,j,lambda}) (label region mass).
Also define the retention condition:
E_{t,j,lambda} = "label lambda is present at BOTH times t-1
and t, and its anchor moved."
The total anchor travel cost is
T_anchor := E sum_{t, j, lambda} r_j b_{t,j,lambda} 1_{E_{t,j,lambda}}.
Note: the factor r_j times b is the "mass times tree-radius"
quantity that pricing an anchor move at scale r_j requires. By the
fixed-alphabet property (Section 10.5), an anchor move is by at
most 40 r_j. So actual displacement in the metric is at most
40 T_anchor.
14.5 What we want.
Proposition (retained-anchor travel). There is an absolute C and a
finite D_anchor, both independent of the input law and horizon,
such that
T_anchor <= C (V + ell P + ell Q) + D_anchor.
This is the last piece before rounding. Combined with V <= C ell P
+ D_T and P <= C ell Q + D_part, it becomes
T_anchor <= C ell^2 Q + D_anchor',
which is exactly the needed order.
14.6 The size tracker.
To pay for anchor movement we need a "per-key normalization" that
stays roughly constant while the underlying key's posterior size
evolves. Fix a heavy label slot lambda at level j. Define
s_{t,j,lambda} := 1 + M_{t,j,lambda},
a positive number in [1, k + 1]. Track it by a held reference
mhat_{t,j,lambda} in [1, k+1]: refresh when a factor rho = 6/5
comparison with the actual s fails. The reference runs all the time,
even while the label is absent, and recycled labels do NOT restart
the tracker. This is essential: no new initialization allowance can
be charged when a label reappears.
The lemma: the total expected refresh cost satisfies
E sum_{t,j,lambda} r_j (mhat_{t-1} + mhat_{t}) 1_{refresh}
<= C ell P + D_size.
The proof uses an entropy trick: the affine tangent of
f(s) = -s log s at u is T_u(s) = u - (1 + log u) s, and the
"return" from u to s at a refresh is
T_u(s) - T_s(s) >= (s + u) / 144,
because the refresh condition implies |s - u| >= (1 - 1/rho)
max(s,u). Then the input contribution to the tangent sum is
O(ell P) via the key-count drift of Section 10.5. And the endpoint
values of the tangent sum are bounded by (k+1)(1+ell) times the
finite number of label slots. So the total refresh charge is
C ell P + D_size.
14.7 The pointwise coefficient bound.
Anchor travel is charged via a potential with COEFFICIENT
b_{t,j,lambda} / mhat_{t,j,lambda}. We need this coefficient to be
summable over scales. The following lemma does it, using both ball
masses in the metric.
Lemma (pointwise parked coefficients). Fix a completed fractional
state (a specific time t) and any y in Y. Let, at each level j with
a heavy center within 7 r_j of y, lambda_j be its (unique) label.
Then
sum over selected j of b_{j, lambda_j} / mhat_{j, lambda_j} <= C ell.
Where "selected" means "a heavy center within 7 r_j of y".
Idea of proof. At a selected level, the heavy ball (radius >= 16 r_j)
contains B(y, r_j), so mhat_j >= (1 + mu(B(y, r_j))) / rho, which
gives a lower bound on the denominator. At the numerator side, use:
sum over selected i >= j of b_i <= C_0 mu(B(y, 67 r_j)),
because for each i, all witnesses lie within 27 r_i <= 27 r_j of y,
and their subtrees have prefix-masses in a set of disjoint depth-j
cells, all within B(y, 67 r_j).
Then the ratio b_j / mhat_j is bounded by
(mu(B(y, 67 r_j)) - previous) / (1 + mu(B(y, r_j))).
Summing this over j is exactly a "ball mass ratio" sum, and the
ball-mass telescope (Section 9.6) bounds it by O(ell). The paper
organizes the details into a dyadic partition of the levels by A_j /
B_j magnitudes. Result: at most 1 + log_2(k+1) dyadic groups, each
contributing at most C.
Consequence: the total coefficient of a point-wise normalized
potential grows only like ell across scales. That is why anchor
travel can be paid by O(V + ell P + ell Q), without a log(J) factor.
14.8 The anchor travel potential.
Define, at each completed state,
Phi_t := sum_{j, lambda} r_j ( b_{t,j,lambda} / mhat_{t,j,lambda} )
* int_{C_{t,j,lambda}} kappa( d(a_{t,j,lambda}, z) / r_j ) dmu_t(z),
where kappa is a clamped ramp:
kappa(u) = 0 for u <= 4,
(u - 4) / 3 for 4 <= u <= 7,
1 for u >= 7.
Interpretation: at each heavy label, we integrate mu (the posterior
counting measure) over its region C, weighted by a normalized ramp
that is 0 near the anchor and 1 for points far from it (>= 7 r_j
away). The pre-factor b / mhat normalizes by the "current size" of
the key.
Bound on Phi: since 0 <= kappa <= 1 and |int| <= M <= mhat, we have
0 <= Phi <= sum r_j b_j <= k r_0 (using that sum of parks over all
vertices is k and each park at depth j has radius r_j <= r_0).
14.9 Decomposing the change of Phi.
The change Phi_{t-1} -> Phi_t is decomposed in five sub-steps,
each handled separately:
1. FILTERING (old parameters held): by concavity, the expected
change is at most 0.
2. DRIFT (physical movement, still at old anchor, old reference,
old park). If the level key changes, we pay at most C r_j by
|b / mhat| <= C_0 and 0 <= kappa <= 1. Summing over the key
disagreement stops per member and over all members gives CP
in expectation. If the key is UNCHANGED, only one hidden
mover moves, and the pointwise coefficient bound (14.7)
charges its small physical movement to at most C ell e_x per
step. Total ell Q.
3. REFRESH size references. When the reference changes r_j b I
(1/s - 1/u), the positive part (only when s < u) is at most
r_j b^{old} <= rho C_0 u times (1/mhat_old before change).
This is at most a constant times the refresh charge, i.e.
C ell P + D_size.
4. UPDATE park amounts. |Delta b| charged by park variation
(14.2): rho (1 + 1/tau) V.
5. UPDATE anchors. A freshly present key had b^{old} = 0, so its
new anchor contribution is rho r_j b^{new} = rho r_j |Delta b|,
again part of the park variation budget. A retained-and-moved
heavy anchor: at a heavy update, the concentration condition
gives a strong inner-mass comparison, and the potential
DECREASES by at least (1/4) r_j b^{new}_{j,lambda}. THIS is
the payment for the specific event we care about.
The last line is the crux. Let's see the details:
At a retained-and-moved heavy label at scale r = r_j:
- The new anchor a_new = x (request).
- Old anchor a_old has d(a_old, x) > 8 r.
- Inner ball B(x, gamma_H r) has mu^+ mass H >= 1 (comparator
covers x).
- New heavy-ball mass satisfies mu^+(C) in [H, (1+delta_H) H].
- New size tracker mhat_new <= rho (1 + mu^+(C)) <= rho (2 + delta_H) H.
- Old ramp kappa(d(a_old, z)/r): for z in B(x, gamma_H r), the
distance d(a_old, z) > (8 - gamma_H) r > 7 r, so kappa = 1.
- New ramp kappa(d(x, z)/r): for z in B(x, gamma_H r), d(x, z) <=
gamma_H r < 4 r, so kappa = 0.
- Change in the ramp at z: -1.
- Extra mass outside the inner ball but inside C contributes at
most delta_H H to the other direction (a bounded increase).
- Net decrease of the potential at this label: at least
(1 - delta_H) H / (rho (2 + delta_H)) * r b_new.
With gamma_H < 1/100 and delta_H < 1/100 and rho = 6/5, this is at
least (1/4) r b_new.
So the event's charge is paid in full by the potential drop. No
extra log, no extra scale factor.
14.10 Putting it together.
Summing the five sub-steps over all t:
Phi_0 - Phi_T + C (V + ell P + ell Q) + D_size >= (1/4) T_anchor.
Using 0 <= Phi <= k r_0, we get the proposition.
14.11 The role in the final bound.
Combined with Section 11's V <= C ell P + D_T and Section 13's
P <= C ell Q + D_part, we get:
T_anchor <= C ell^2 Q + D_anchor'.
So anchor travel is "the same order as the rest". This is the last
piece needed before rounding.
------------------------------------------------------------------------
15. ROUNDING: FROM FRACTIONAL MASS TO INTEGER SERVERS
------------------------------------------------------------------------
Everything so far produces REAL masses q_v on the tree, and REAL
parks p_v^circ = q_v - sum_children q_i. But actual servers are
DISTINCT; there are exactly k of them; each occupies ONE tree
vertex. We need to round.
15.1 The problem.
Find integer quantities n_v(t) and c_v(t) at each vertex, with:
n_root(t) = k
n_v(t) = c_v(t) + sum_children n_i(t) for internal v
c_leaf(t) = n_leaf(t) (leaves have no children)
n_v(t) in {floor(q_v(t)), ceil(q_v(t))} (balanced rounding)
c_v(t) in {floor(p_v^circ(t)), ceil(p_v^circ(t))}
E[n_v(t) | F_t] = q_v(t), E[c_v(t) | F_t] = p_v^circ(t)
The first four are unconditional properties of ROUNDING; the last
three are EXPECTATION identities (unbiased at every vertex).
The integer "parks" c_v(t) tell us how many servers occupy vertex v
at time t. Total across all v is exactly k. Children inherit their
subtree counts from c_v.
15.2 A local rounding lemma (the key building block).
This one lemma is the crown jewel of the rounding section. Here is
the exact statement.
Lemma (balanced rounding with prescribed random total). Let
a = (a_1, ..., a_d) and b = (b_1, ..., b_d) be nonnegative real
vectors. Let X be a random integer vector with
X_i in {floor(a_i), ceil(a_i)} for every i,
E X_i = a_i for every i.
Let M = sum_i X_i. Also, N is any random integer with
N in {floor(sum b_i), ceil(sum b_i)},
E N = sum b_i.
Then there is a randomized kernel from (X, N) to integer vectors X'
such that for EVERY state (X, N) and EVERY outcome of the kernel,
X'_i in {floor(b_i), ceil(b_i)},
sum_i X'_i = N,
E[X'_i] = b_i (averaged over both X, N and the kernel).
The expected L1 cost is bounded by
E ||X' - X||_1 <= 32 T + 11 I,
where T = sum_i |a_i - b_i| and I = E |N - M|.
The heart of the proof is a "repair by exchanges" argument. Here
is the idea:
STEP 1 (clip). For each coordinate, clip X_i to [floor(b_i),
ceil(b_i)]. Let Y be the clipped vector. Then
E |Y_i - X_i| <= |a_i - b_i|,
because at most one side of the interval can differ from a_i's
neighborhood. So sum over i of E |Y_i - X_i| <= T.
STEP 2 (adjust to N). For each realized state (Y, N), adjust
coordinates up or down until the sum equals the actual N, obtaining
Z. This is always possible: the set of achievable integer sums
within the box is every integer between sum floor(b_i) and
sum ceil(b_i), and N lies in that set. The adjust cost is exactly
|N - sum Y_i|, so
E ||Z - X||_1 <= 2T + I.
STEP 3 (repair means). Now Z has the right fixed-total property in
each state but the coordinate means E Z_i may not equal b_i. The
discrepancy D := sum_i |E Z_i - b_i| <= 3T + I.
To fix the means, choose a finite joint kernel p_state (a
probability distribution on "which coords to round up" per state,
preserving the per-state total). Consider the finite-dimensional
convex optimization:
minimize E[|A symdiff A_0|] + 10 sum_i |Pr(i in A) - f_i|,
where A_0 is Z's rounding-up-set (from Step 2), f_i = b_i -
floor(b_i) is the fractional part, and A ranges over allowed
rounding-up-sets (those of size (N - sum floor(b_i))). Compactness
of the domain gives a minimum.
If a marginal Pr(i in A) is bigger than f_i for some i and
smaller for some j, one of two local exchanges strictly improves
the objective:
(a) If some supported pair (state, subset) has i in A and j not
in A: swap i out and j in, on a small mass epsilon. Total per
state is preserved. Sum of marginal discrepancies drops by
2 epsilon. Hamming cost rises by at most 2 epsilon. Strict
improvement, contradiction.
(b) Otherwise, no supported subset has i without j. Then find one
with both, one with neither, one h in the second but not the
first (cardinalities differ by at most 1, so such an h exists),
and swap. Now it is i out, h in on the first subset and h out,
j in on the second. Sum of marginals moves in the right
direction on i and j and leaves h alone. Hamming cost rises by
at most 4 epsilon. Strict improvement, contradiction.
So at a minimizer, Pr(i in A) = f_i for all i, giving E X'_i =
b_i.
STEP 4 (compare). The kernel X' equals Z everywhere up to a
Hamming correction, with E ||X' - Z||_1 <= 10 D <= 10 (3T + I).
Combining: E ||X' - X||_1 <= (2T + I) + 10(3T + I) = 32 T + 11 I.
The lemma is self-contained, entirely finite, and needs NO
independence assumption between X and N. Exactly what we need for
top-down rounding.
15.3 Top-down rounding through the tree.
Apply the lemma recursively from the root down. At every internal
v, treat the "star" whose coordinates are:
(children of v) x (one coordinate for v's own park).
Target vector b = (q_i)_{i child of v} x (p_v^circ). Sum of
targets is q_v (exactly the allocation rule). Current X = previous
step's rounded children and park. The prescribed total N is n_v(t),
the already-generated rounded parent count.
By induction, at each v we have:
sum of children counts + park count = n_v(t) (in every state),
E[child i count | F_t] = q_i(t),
E[park count | F_t] = p_v^circ(t).
At the root, n_root = k is fixed. So the sum of all parks is k in
every realized state.
15.4 Bounding the tree movement.
Let N_rnd := E sum_t sum_{v != root} r_{|v|-1} |n_v(t) - n_v(t-1)|.
The lemma's 32 T + 11 I structure combines with the totals over
the tree via a simple absorption. The parent's own |Delta n_v|
term appears with coefficient 11 at star v. The 32 factor multiplies
the T terms at v, which are O(sum children + own park) = O(V)
per step.
Result: with tau >= 22 (a specific numerical requirement), one has
N_rnd <= 132 V.
Note the 132 is 4 x 33 roughly: it comes from (64 + 32/tau) V +
(11/tau) N_rnd, then solving for N_rnd <= (128 + 64/tau) V <=
132 V.
15.5 Tree matching (from rounded parks to actual positions).
We have integer parks c_v(t) at each vertex. Each vertex is a
"supply" of c_v(t) units, or a "demand" if the local integer
count declined. We want a matching cost bound per step.
Match min{c_v(t-1), c_v(t)} copies AT the same vertex; these cost
zero TREE distance (they may cost something metric if their anchor
moved, handled separately below). The unmatched copies form an
integer supply-demand problem on the tree.
Standard tree-matching lemma:
match supplies to demands by canceling them node-by-node,
bottom-up, propagating uncancelled copies to the parent.
The total TREE distance traveled by an integer unit is exactly the
sum over nonroot vertices of (edge length entering v) * |Delta n_v|,
where n_v is the total subtree count. Because the subtree imbalance
is exactly Delta n_v, and that must cross the entering edge.
So the tree matching cost per step is at most
sum over v != root of r_{|v|-1} |n_v(t) - n_v(t-1)|.
15.6 Realizing on the metric space Y.
We have integer "parks" at tree vertices. We now place those copies
in the ACTUAL metric Y, using the anchors:
A copy parked at a nonroot vertex v is placed at the current
anchor of v's last key.
A copy parked at the root is placed at a fixed reference point
of Y.
The matching of consecutive configurations in the METRIC: the tree
matching suggests a "path" per matched copy. If two copies matched
at the SAME vertex v are placed at its (consecutive) anchors, their
metric distance is bounded by the anchor travel T_anchor (paid by
Section 14). If two copies matched at DIFFERENT vertices u (old)
and v (new), we need to bound their metric distance.
Lemma (metric cost of distinct-vertex tree match). Let u (old) and
v (new) be vertices matched by the tree matching. Let j be the
depth of their lowest common ancestor. Then
d(a_-(u), a_+(v)) <= 120 r_j,
where a_-(u) is u's old anchor and a_+(v) is v's new anchor. And
r_j is at least the tree path length between u and v.
So metric matching cost <= 120 times tree matching cost.
15.7 Total rounding + realization.
Combining:
E[ total simulated metric movement ]
<= 120 N_rnd + 40 T_anchor
<= 120 * 132 V + 40 T_anchor.
Justification of the second summand: a matched pair at the SAME
vertex v could have moved (bounded by 40 r_{|v|}, hence by T_anchor
when paid per unit of parked mass). The 40 comes from the heavy
reuse displacement bound (Section 10.5).
15.8 Combining with Sections 11-14.
Plug in:
N_rnd <= 132 V,
V <= C_1 ell P + D_T,
P <= C_P ell Q + D_part,
T_anchor <= C_T (V + ell P + ell Q) + D_anchor.
Then:
E[ total simulated metric movement ]
<= C_1 * V + C_2 * ell P + C_2 * ell Q + D_{sim},
for absolute C_1, C_2 and finite D_{sim}, which is exactly
<= C_sim ell^2 Q + D_{sim}'.
And by the lazy simulation lemma (Section 8), the ACTUAL cost on
real servers is at most the simulated cost plus the one-time
initial matching distance between the actual start and the initial
simulated configuration. Giving the choice of zero initial mismatch
(cf. the fixed-alphabet construction) or the bounded k*diam
initial mismatch, this completes the "finite distributional
estimate" (Proposition in Section 9).
15.9 Chained bound.
Combining the layers:
V <= 12 C_A ell P + D_A,
P <= C_P ell Q + D_P,
T_anchor <= C_T (V + ell P + ell Q) + D_T,
N_rnd <= 132 V,
sim-cost <= 120 N_rnd + 40 T_anchor,
actual <= sim-cost + initial_mismatch.
Plug in from the bottom up:
sim-cost <= C_1 V + C_2 ell P + C_2 ell Q + D_sim
<= C_1 (12 C_A ell P + D_A)
+ C_2 ell (C_P ell Q + D_P)
+ C_2 ell Q + D_sim
<= C_3 ell^2 Q + D_sim'.
Where C_3 collects the coefficients. And then
actual <= C_3 ell^2 Q + D_sim' + k * diam(Y) * 1_{start not perfectly covered}.
So we have a policy whose expected cost is <= C_3 ell^2 Q + D_0
for SOME absolute C_3 and a fixed finite D_0.
This is exactly Proposition (finite distributional estimate) in
Section 9. The rest of the paper transfers this to actual policies
on arbitrary metric spaces.
------------------------------------------------------------------------
16. TRANSFER: FROM ONE LAW TO ONE POLICY ON ANY SPACE
------------------------------------------------------------------------
Everything above proves: for a FIXED finite metric space Y, FIXED
horizon H, FIXED probability law on Y^H, and FIXED starting tuple s,
there is a policy with
E[cost] <= a * ell^2 * E[OPT] + D_0(Y, k, s),
where a is an absolute constant and D_0 is a fixed finite number
depending only on (Y, k, s), not on the law or on the horizon.
We now remove the law, the horizon, the finiteness of Y, and the
additive term. Four steps.
16.1 What needs to be removed.
The finite-law statement has FOUR "undesirable" dependencies:
(i) It assumes a specific finite probability law on Y^H.
We want a policy that works for a single fixed sequence,
not just in expectation over a random one.
(ii) It has an additive constant D_0.
We want D_0 = 0, at least when starting positions are
distinct.
(iii) It works on the specific finite metric Y.
We want a statement for an ARBITRARY metric space, which
can be infinite and have no minimum gap.
(iv) It depends on the horizon H.
We want one policy that works for every finite H
simultaneously.
Steps 16.2 through 16.5 handle these four in order.
16.2 Episode amplification: remove the additive term.
Fix Y finite, k >= 2, and a starting tuple s = (s_1, ..., s_k) with
DISTINCT entries. Fix any finite-support law lambda on finite
sequences in Y.
Claim (goal of this subsection). There is a policy A_lambda, causal
and strongly lazy, such that for every sigma in the support of
lambda:
E[cost_{A_lambda, s}(sigma)]
<= alpha * OPT(s, sigma),
with alpha := (2a + 1) * ell^2.
No additive term. Note that A_lambda does NOT depend on sigma, but
it DOES depend on lambda. This is a "finite-law" policy.
Later (Section 16.3) we upgrade to a single policy independent of
lambda.
THE PADDED WORD. Let L = max(1, max |sigma| over support of
lambda). Extend every sequence sigma in the support to a padded
word rho of exactly L requests, by repeating its last request. (If
sigma is empty, use L repetitions of s_1.)
Padding does NOT change OPT:
OPT(s, rho) = OPT(s, sigma),
because:
- Restricting a legal service of rho to its first |sigma| slots
already serves sigma, so OPT(s, sigma) <= OPT(s, rho).
- An optimal service of sigma is trivially extended to rho by
moving nothing on the repeated request: the last request is
already covered. So OPT(s, rho) <= OPT(s, sigma).
THE REVERSE WORD. For each padded word rho, choose (deterministic
tie-breaking) ONE optimal service from s. Let C_t(rho) be the
configuration chosen by that optimal service at time t, and let
j_t be the label of the server moved at time t. Define the reverse
word:
rho_leftarrow := ( C_{L-1,j_L}(rho), C_{L-2,j_{L-1}}(rho),
..., C_{0,j_1}(rho) ).
Interpretation: this is a length-L word that is legally served by
the single server j_L moving first, then j_{L-1}, ..., then j_1.
If you start from C_L(rho) and do exactly those single-server
moves, you retrace the original optimal service BACKWARD and return
to C_0 = s, at the same total cost OPT(s, rho).
THE RESET WORD. Given the distinct starting tuple s, define the
reset word as R repetitions of the k symbols (s_1, ..., s_k), where
R = floor( k * diam(Y) / delta ) + 1.
Here delta is the minimum gap between distinct points of Y (defined
in Section 7.5). The reset word is served by moving each server to
its own starting point in order; the cost at each move is at most
diam(Y); total reset cost is at most R * k * diam(Y), which is
finite.
THE CONCATENATED EXPERIMENT. Fix an integer N >= 1. Sample N
independent words rho_1, ..., rho_N from lambda. Concatenate for
each i its forward word, its reverse word, and the reset word:
sigma_N := rho_1 rho_1_leftarrow (reset) rho_2 rho_2_leftarrow (reset) ... rho_N rho_N_leftarrow (reset).
The total length is fixed: N * (2L + Rk). The law of sigma_N is a
fixed finite-support probability distribution that DOES NOT DEPEND
on the policy.
AN OPTIMAL SERVICE OF sigma_N. Use the previously chosen optimal
service on each forward word, its reverse on each reverse word,
and the obvious reset on each reset block. The total cost obeys:
cost of this service of sigma_N
<= sum_i (2 OPT(s, rho_i)) + sum_i (reset cost) (reset cost
is 0 at the boundary between blocks).
= 2 sum_i OPT(s, rho_i).
In expectation over rho_1, ..., rho_N drawn from lambda:
E[ OPT(s, sigma_N) ]
<= 2N * E_{rho ~ lambda}[OPT(s, rho)]
= 2N * Q_lambda,
where Q_lambda := E_{rho ~ lambda}[OPT(s, rho)].
THE FINITE-LAW POLICY ON sigma_N. Apply the finite distributional
estimate (Section 15) to sigma_N under its law. This gives a policy
A_N, causal and strongly lazy, with
E[ cost_{A_N, s}(sigma_N) ]
<= a ell^2 * E[ OPT(s, sigma_N) ] + D_0(Y, k, s)
<= a ell^2 * (2N Q_lambda) + D_0.
EXTRACTING ONE FORWARD BLOCK. Run A_N on sigma_N. Let F_i, H_i, Z_i
be its costs on the i-th forward block, its i-th reverse block, and
its i-th reset block. Let A_i be its configuration at end of block
i's reset word. Set M_i := M(A_i, s) = matching distance from A_i
to s. And M_0 := M(s, s) = 0 (the start).
Claim (pathwise): M_i <= Z_i for every i.
Why? If Z_i = 0, the actual policy did not move during the reset
block. A full reset cycle of zero movement leaves the multiset of
server positions unchanged. Because there are exactly k servers
and k distinct starting points, the multiset must be exactly s. So
M(A_i, s) = M(A_{i-1}, s) = ... = M(A_0, s) = 0, so M_i = 0 <=
Z_i.
If Z_i > 0, then during the reset cycle some server moved. Because
the reset word visits each of s_1, ..., s_k in order and the
policy is strongly lazy, either a move occurs (in which case
Z_i >= shortest nonzero move distance = k * delta > k * delta/2),
or the configuration already matches s up to permutation and M_i
= 0. So M_i <= k delta/2 < Z_i in the positive case. Uniformly
M_i <= Z_i holds.
THE "EXTRACT A FORWARD BLOCK" CONSTRUCTION. Now:
- Set I = uniform in {1, ..., N}.
- Sample sigma ~ lambda.
- Run A_N virtually on the concatenation from 1 through forward
block I (all the previous blocks included), starting at s.
- Let A be the resulting policy's configuration on the current
forward block plus its starting history.
Define the actual policy A_lambda by running this construction
fresh at each request, always with I = "current block" and using
the finite-law policy A_N to define the virtual evolution.
Because of lazy simulation (Section 8), the actual policy's cost
on the current forward block is at most (virtual cost through this
block) + M_{I-1} (initial mismatch between A_{I-1} and s).
Summing expectations:
E[ cost_{A_lambda, s}(sigma) ]
<= (1/N) sum_{i=1}^N E[ F_i + M_{i-1} ]
<= (1/N) sum_{i=1}^N E[ F_i + Z_{i-1} ]
= (1/N) E[ (sum F_i) + (sum_{i < N} Z_i) ]
<= (1/N) E[ cost_{A_N, s}(sigma_N) ].
The last inequality drops the H_i and Z_N terms because they are
nonnegative.
Plugging in the total bound:
E[ cost_{A_lambda, s}(sigma) ]
<= (1/N) [ a ell^2 * 2N Q_lambda + D_0 ]
= 2a ell^2 * Q_lambda + D_0 / N.
Finally CHOOSE N large enough that D_0 / N <= ell^2 * Q_lambda:
N = max( 1, ceil( D_0 / (ell^2 * Q_lambda) ) ),
and obtain
E[ cost_{A_lambda, s}(sigma) ]
<= (2a + 1) ell^2 * Q_lambda
= alpha * OPT(s, sigma).
This completes 16.2. Note: N depends on the law lambda, but NOT on
any realization of sigma_N. The policy A_lambda itself is a fixed
causal strategy.
16.3 Finite-family separation via Yao.
Now fix Y finite, k >= 2, s with distinct entries, and any FINITE
collection sigma_1, ..., sigma_m of finite sequences in Y. We will
construct one behavioral policy p that satisfies
E[ cost_{p, s}(sigma_i) ]
<= alpha * OPT(s, sigma_i) for every i = 1, ..., m.
This is the "finite minimax" lemma.
THE SET OF DETERMINISTIC POLICIES IS FINITE. For any fixed finite
set of sequences, only finitely many decision histories arise.
Enumerating all deterministic causal policies for those histories
gives a finite set D of policies. For each policy pi in D, define
v(pi) := ( E[cost_{pi, s}(sigma_1)] - alpha OPT(s, sigma_1),
...,
E[cost_{pi, s}(sigma_m)] - alpha OPT(s, sigma_m) ).
Each v(pi) is a vector in R^m.
WE WANT A MIXTURE OF D WITH NONPOSITIVE EXCESS VECTOR. Let K =
convex hull of { v(pi) : pi in D }.
Claim: K intersects the closed negative orthant (-R_{\ge 0})^m.
Proof by contradiction. Suppose K does not intersect the negative
orthant. Then there is a separating weight vector w in the relative
interior of the unit simplex in R^m, such that for every pi in D,
sum_j w_j * excess_{pi}(sigma_j) > 0.
(Standard convex-separation + compactness of the closed intersection
test.) But the w_j are nonnegative and sum to 1, so they define a
probability distribution on { sigma_1, ..., sigma_m }. Section 16.2
applied to just this finite law (which has support within the finite
set of the sigma_j's) gives a policy A_w with
E_{j ~ w}[ cost_{A_w, s}(sigma_j) - alpha OPT(s, sigma_j) ] <= 0.
The LEFT side is a mixture of excesses over deterministic policies?
Not quite: A_w is potentially RANDOMIZED (from Section 16.2, it uses
internal coins). But its cost is a probability mixture of some
deterministic policies' costs. So the average over the deterministic
policies must be nonpositive against the same weight w, contradicting
"strictly positive for every pi in D".
Hence K does intersect the negative orthant. That gives a MIXTURE
theta over D with:
sum_pi theta_pi * E[cost_{pi, s}(sigma_j)]
<= alpha OPT(s, sigma_j) for every j.
Now we have a message: "sample pi from theta at the start and run
it". This uses ONLY the sum_j coordinate checks, and the mixture's
cost on sigma_j is exactly the above. So the mixture works.
BEHAVIORAL CONVERSION (KUHN). A mixture over D is still a
"correlated" object: the same pi is drawn once at the start and
used for the whole sequence. We want a "behavioral" policy, where
AT EACH HISTORY the policy can independently flip its own coins,
without keeping the global pi in mind. That is what a real online
policy does.
For perfect-recall games (and finite-sigma games have perfect
recall), the mixed / behavioral distinction is empty: Kuhn's
theorem. Concretely, at every decision history h = (prefix, label
history), define:
Z(h) := sum_{pi in D(h)} theta_pi,
p_h(j) := [sum_{pi in D(h): pi(h) = j} theta_pi] / Z(h)
for j = 1, ..., k, where D(h) is the subset of D that would have
chosen exactly the observed label history through h. If Z(h) = 0,
put any probability vector (e.g. all mass on j = 1).
Induction on t shows that at every reachable label history on
sigma_i, the probability of reaching it under the behavioral
policy equals its theta-mixture probability. So the LABEL
DISTRIBUTIONS, and therefore the COSTS, are the same. The behavioral
policy p hence satisfies
E[ cost_{p, s}(sigma_i) ]
<= alpha OPT(s, sigma_i) for every i = 1, ..., m.
16.4 Compactness via Tychonoff: one policy for every finite input.
Now drop the finiteness of the sequence collection. Fix Y finite and
s distinct. Let the "policy set" be the product space
P := prod_{h} Delta_k,
where h ranges over ALL decision histories (prefix of a sequence in
Y and label history), and Delta_k is the k-dimensional probability
simplex. P is a product of finitely many compact spaces, so P is
compact by Tychonoff's theorem.
For each finite sequence sigma in Y and each behavioral p in P,
define
Phi_sigma(p) := E[cost_{p, s}(sigma)] - alpha OPT(s, sigma).
Each Phi_sigma is a function from P to R. Compactly: at fixed
sigma, only finitely many h matter, so Phi_sigma is a polynomial
in the finitely many coordinates p_h it depends on. Hence
Phi_sigma is continuous on P.
For each finite collection { sigma_1, ..., sigma_m }, Section 16.3
gives p_thetasigma with Phi_{sigma_i}(p) <= 0 for every i. So the
closed sets { p : Phi_sigma(p) <= 0 } for all sigma simultaneously
satisfy the finite-intersection property: every finite subfamily
has nonempty intersection. So the whole family has nonempty
intersection (P compact).
Take p_* in that intersection. Then
E[ cost_{p_*, s}(sigma) ]
<= alpha OPT(s, sigma) for every finite sigma.
This is the "one behavioral policy for every finite input".
REALIZATION. Take a single uniform seed omega in [0, 1). At
each decision history h with probability vector p_h, subdivide the
current interval into k pieces of relative lengths p_h(1), ...,
p_h(k), choose the piece containing omega, and iterate with the
resulting interval. This realizes p_* as a genuine randomized online
policy, one strategy for every input, defined WITHOUT a horizon.
16.5 Repeated starting positions.
Now drop the distinctness of s.
Fix Y finite, k >= 2, and any starting tuple s = (s_1, ..., s_k)
in Y^k. Choose any tuple u = (u_1, ..., u_k) of k DISTINCT points
of Y. Such u exists because |Y| >= k+1 by assumption.
Let D = M(s, u), the matching distance between s and u. Since
there are finitely many permutations of {1, ..., k}, D is finite.
SERVICE COMPARISON. For any finite sigma in Y:
OPT_u(sigma) <= OPT_s(sigma) + D.
Proof: Take any optimal service from s of total cost OPT_s(sigma).
Follow this service with the SAME sequence of physical moves applied
to servers starting at u. The MOVES (which server, where to) are
identical; the only difference is the initial positions. So the
overall cost is at most (initial matching distance) + OPT_s(sigma)
<= D + OPT_s(sigma). This is a legal service from u. Hence OPT_u
<= D + OPT_s. (The lazy simulation lemma gives the same comparison.)
POLICY. Apply Section 16.4 to u: build a behavioral policy A_u
satisfying
E[cost_{A_u, u}(sigma)] <= alpha OPT_u(sigma) for every sigma.
Now run A_u VIRTUALLY. At each request, follow its configurations
in Y from virtual start u. Lift its current configuration C_t to an
actual configuration A_t on Y at ACTUAL start s using the lazy
simulation lemma (Section 8): take the minimum matching from C_t to
the CURRENT actual configuration A_{t-1}, and where a request needs
a server at r_t, move the matched ACTUAL server to r_t.
Pathwise:
cost_{A, s}(sigma) <= cost_{A_u, u}(sigma) + D.
Take expectation:
E[cost_{A, s}(sigma)]
<= E[cost_{A_u, u}(sigma)] + D
<= alpha OPT_u(sigma) + D
<= alpha (OPT_s(sigma) + D) + D
= alpha OPT_s(sigma) + (alpha + 1) D.
Set B := (alpha + 1) D. This depends only on (Y, k, s) and not on
sigma or on |sigma|. When s has distinct entries we may take u = s
and get B = 0.
16.6 Final constants and the absolute-constant statement.
We have established: for Y finite, k >= 2, starting tuple s, there
is a behavioral policy A = A_{Y, k, s} with
E[cost_{A, s}(sigma)]
<= (2a + 1) ell^2 OPT_s(sigma) + B,
where:
a is an absolute constant from Section 15 (typically around
10^6 in the proof, but the exact value does not matter),
ell = 1 + log(k + 1),
B = (alpha + 1) D is a fixed finite number depending only on
(Y, k, s), and B = 0 when s has distinct entries.
To absorb the "+1" in ell: since k >= 2, ell >= 1 + log 3 > 1 > 0,
so we can write
ell^2 = (1 + log(k+1))^2 <= 4 * (log(k+1))^2.
So with C = 4 (2a + 1):
E[cost_{A, s}(sigma)]
<= C (log(k+1))^2 OPT_s(sigma) + B.
Finally, the Y-finiteness: any finite metric statement extends to
an arbitrary metric space X by choosing Y = support of the given
finite sigma plus u plus s (finitely many points!) as the
relevant finite metric, noting that the statement depends only on
Y. The general conclusion is thus:
For every metric space X with at least k+1 points, every k >= 2,
and every starting tuple s in X^k, there is a behavioural
policy A on X with
E[cost_{A, s}(sigma)] <= C (log(k+1))^2 OPT_s(sigma) + B
for every finite sigma in X^*, where C is absolute and B is a
fixed finite number depending only on (X, k, s), and B = 0 when
the entries of s are distinct.
This is the main theorem. Done.
------------------------------------------------------------------------
17. ASSEMBLING THE FINAL BOUND: WHERE EACH LOG LIVES
------------------------------------------------------------------------
This section tells the "money chain" of the proof. Each link is a
lemma we have already explained. Read top-down for the composite;
read bottom-up for the money flow.
17.1 The three budget inequalities.
The three moving pieces are:
(Chain 1) Allocation (Section 11):
V <= 12 C_A ell P + D_A.
V = E sum_t sum_{v != root} r_{|v|-1} |Delta q_v|.
The movement of the TREE ALLOCATION.
(Chain 2) Partitions (Section 13):
P <= C_P ell Q + D_part.
P = E sum_t sum_a d_T( xi_{t-1}(X_{t-1}^a), xi_t(X_t^a) ).
The movement of the hidden comparator on the tree.
(Chain 3) Anchor travel (Section 14):
T_anchor <= C_T ( V + ell P + ell Q ) + D_anchor.
T_anchor = E sum_{t,j,lambda} r_j b_{t,j,lambda} 1_{E}.
The expected mass-times-radius of moving anchors.
Chain 1 costs ell per unit of comparator movement (P). Chain 2 costs
ell per unit of offline optimum (Q). Chain 3 costs (V + ell P + ell Q)
and introduces no new factor of ell.
17.2 Rounding and realization (Section 15).
(R1) N_rnd <= 132 V,
where N_rnd := E sum_t sum_{v != root} r_{|v|-1} |Delta n_v|.
(R2) E[simulated movement] <= 120 N_rnd + 40 T_anchor.
Both have fixed absolute factors. No ell and no k in them.
17.3 The plugin.
Substituting R1 into R2 and then Chain 1 and Chain 2:
N_rnd <= 132 (12 C_A ell P + D_A)
= 132 * 12 C_A ell P + 132 D_A.
sim <= 120 (132 * 12 C_A ell P + 132 D_A)
+ 40 C_T (V + ell P + ell Q)
+ 40 D_anchor
<= 120 * 132 * 12 C_A ell P
+ 120 * 132 D_A
+ 40 C_T (12 C_A ell P + D_A)
+ 40 C_T ell P
+ 40 C_T ell Q
+ 40 D_anchor
= [coefficient of ell P] ell P
+ [coefficient of ell Q] ell Q
+ [constant].
Because P <= C_P ell Q + D_part:
[coefficient of ell P] ell P
<= [coefficient] ell (C_P ell Q + D_part)
= [coefficient * C_P] ell^2 Q + [coefficient] ell D_part.
Collecting:
sim <= C_sim ell^2 Q + D_sim'
for absolute C_sim and finite D_sim'. Add the one-time initial
mismatch (from lazy simulation, at most k * diam(Y)) to reach the
ACTUAL cost:
actual <= C_sim ell^2 Q + D_0.
This is the finite-distributional estimate used in Section 16.2.
17.4 Where the two logarithms come from.
THE FIRST ell comes from Section 11 (allocation).
It is the factor C_A ell in V <= 12 C_A ell P.
THE SECOND ell comes from Section 13 (partitions).
It is the factor C_P ell in P <= C_P ell Q.
Sections 12, 14, and 15 add only CONSTANT overhead on top of an
already-log-costed quantity. They introduce no further logarithm.
So the two logarithms are structurally: one for the tree
allocation, one for the changing partitions. This is the "sharp
squared-logarithmic" structure. Many earlier results had
O(log^2 k * log n) or O(log^2 k * log Delta) or worse; every such
factor was an artifact of embedding statically. Here the embedding
CHANGES with the requests, and the pilot potential pays for each
change.
17.5 Why log n and log Delta were defeated.
- A static embedding of a metric loses a factor of log n.
- A changing embedding avoids that loss, but then each partition
edit needs payment.
- The PILOT POTENTIAL (Section 12) lets each edit be paid for
with the LOCAL mass-ratio coefficient, not a global worst case.
- The BALL-MASS TELESCOPE (Section 9.6) sums the local ratios
across scales with a coefficient that depends only on the RATIO
of masses, not on n.
- The remaining "how many levels" factor is bounded by the
telescoping sums as ell, not as log n or log Delta.
The "agnostic" log(k) bounds with no dependence on the metric size
or aspect ratio are therefore obtained.
17.6 How the sharpness matches the lower bound.
BCR 2023 gives (Corollary 20) a universal Omega(log k) lower bound on
every metric with more than k points, and (Theorem 11 plus
Proposition 8) a metric with only k+1 points where Omega(log^2 k)
is required even with a fixed additive constant.
Our upper bound matches the second one order-for-order. It is "sharp
in the worst case": on SOME metric the true optimal competitive
ratio is Theta(log^2 k), and our policy attains O(log^2 k).
For SMALLER families of metrics (paging, HSTs, etc.), tighter bounds
continue to hold; the theorem is a worst-case over metrics and does
not claim to be tight on any particular family.
17.7 The proof is explicit (in principle).
Every lemma is a closed-formula object:
- l^beta is a convex piecewise function with explicit constants.
- The simplex tracker is an argmin of an explicit integral.
- The pilot potential is a specific finite-dimensional min.
- The rounding lemma is a specific local exchange.
You can in principle SIMULATE every piece. The proof does not
address complexity; polynomial-time versions require separate
work (Coester-Cosson 2026), and the theorem we are explaining
makes no such claim.
------------------------------------------------------------------------
18. HONEST LIMITS: WHAT THE PAPER DOES NOT CLAIM
------------------------------------------------------------------------
18.1 No efficiency.
The theorem asserts EXISTENCE of a policy with the stated
competitive ratio. It says nothing about whether you can compute
the policy's next move in polynomial time. The compactness
construction (Section 16.4) is thoroughly non-constructive. For
implementations, extra work is needed, and that work belongs to
separate literature.
18.2 No tight constants.
The universal constant C in the main theorem is astronomical (a
product of many "12 C_A C_P ..." hiding several hundred digits of
internal absolutes). The paper does not try to minimize C. It could
be 10^50 and the theorem would still hold. The point of O(log^2 k)
is the asymptotic growth rate in k.
18.3 The additive term is real.
When two starting servers occupy the SAME point, the additive term
B cannot generally be zero. The episode amplification produces
B = (alpha + 1) D where D = M(s, u) is the matching distance to the
nearest DISTINCT tuple u. There is no claim to remove B in this
case.
18.4 No new lower bound.
The paper proves an upper bound. It does not prove a matching lower
bound. It uses the existing Omega(log^2 k) lower bound of BCR 2023.
The theorem is "matches the known lower bound", not "discovered the
true factor".
18.5 No claim of "best possible for each metric".
The O(ell^2) bound is tight OVER ALL METRICS. On specific metrics
the true optimum may be smaller. The theorem does not claim to be
tight on paging, on HSTs, on trees, or on any particular family.
18.6 No "natural" online rule.
The construction uses:
(i) a finite distributional estimate that depends on the input
law;
(ii) episode amplification to remove that law;
(iii) Yao / Kuhn to reach a single behavioral policy on finitely
many inputs;
(iv) Tychonoff compactness to reach one policy for every input.
At no point is there a "simple, human-improvise-this" rule. That is
by design: the point is existence, not implementation.
18.7 What "log" means.
All logarithms are natural (base e). Base-2 logarithms differ by a
fixed constant (1/ln 2), and the statement C (log)^2 with an
absolute C is unchanged in order by switching bases.
18.8 What the metric space can be.
Nonempty and with at least k+1 points. Otherwise the deterministic
lower bound "more than k points" is not present, and the offline
game is trivial (all requests can be served at cost 0 if the metric
has at most k points).
18.9 B is finite in principle.
For an infinite metric, D = M(s, u) is a minimum over FINITELY many
permutations, and each d(s_i, u_{pi(i)}) is a finite real number by
the metric axioms. So D is finite, so B = (alpha + 1) D is finite.
B may be huge, but it is finite.
18.10 What if the metric has no minimum gap?
The "minimum gap delta > 0" is used only inside the fixed-finite-Y
analysis (Section 7.5) to make level-J cells singletons. In the
final theorem, Y is replaced by the finite support of the actual
sequence: only finitely many points ever appear, so delta > 0 always
holds there. Hence no discreteness assumption is needed at the level
of a final theorem statement.
------------------------------------------------------------------------
19. A ONE-PAGE GLOSSARY
------------------------------------------------------------------------
SYMBOLS (alphabetical):
A, A_t Actual labelled server configuration at time t. The
context distinguishes ACTUAL A from SIMULATED
configurations C_t.
A_s A behavioral strategy starting from tuple s.
A_j Alphabet at tree level j. A finite set of labels.
B Additive correction in the main theorem. Depends only
on (metric, k, starting tuple). Zero when starting
positions are distinct.
beta_v The rank-function parameter at tree vertex v, in
[3, 3 + epsilon_*]. Explicit in terms of M_v.
C Generic absolute constant. Also C_0, C_1, C_A, C_P,
C_T, C_sim, C_final. All fixed numbers.
c_v(t) Integer "park" at tree vertex v at time t: how many
simulated servers occupy vertex v.
C_loc Local Lipschitz constant of the pilot integrand near
a concentrated request (Section 12.6).
d(x, y) Distance in the metric.
D_*, D_1 Pilot template "outer radius" constants. Also
D_H, D_L heavy-template and tier-template outer radii:
D_1 = 10 D_* = 100 R (heavy template),
D_L = 100 R = 400 D_H (tier template).
D_T, D_A, Fixed additive constants in the budget inequalities.
D_P, D_part Each depends on (tree, radii, k), never on the input
law, on the horizon, or on the number of histories.
diam(Y) Diameter of the (finite) metric.
delta Minimum nonzero distance in the finite metric.
e_x Expected mover distance for request x:
int d(x, y) dnu(y). Sum over t of E[e_{r_t}] = Q.
ell Little ell: 1 + log(k+1). Order log k.
epsilon_* = 1/100. Upper end of the useful interval for beta.
eta_i = c_t h_i / ell. Tolerance in the alpha feasibility
constraint.
F_t Filtration at time t. Generated by r_1, ..., r_t and
any independent partition tape.
F_z^g Pilot integrand:
(1+g(p)) (1 - sum_s z_s b_s(p))
+ 256 sum_s z_s (1+g(s)) a_s(p).
gamma_H, Inner radii of the heavy template and the tier
gamma_L template, both < 1/100.
h_i log(M_v / M_i). Size of child i relative to its
parent. Bounded in [0, C ell].
H Horizon (number of requests). Also "H = 1 + log(1/u)"
in one dominant-child inequality; context names it.
H_k Set of tiers, {1, 2, 4, ..., 2^b}, of size
1 + floor(log_2 log k).
K_h = ceil(e^{C_K h}). Age threshold for tier h. Also
serves as the density parameter for tier-h radii.
k Number of servers.
L Length of a padded word in episode amplification.
l^beta The rank function: convex, nonincreasing, equal to
1 - beta p on [0, p_*], and zero from s_* on.
L_v^beta Rank aggregation sum_a l^beta(p_{va}) at vertex v.
M_v Size aggregation sum_a l^siz(p_{va}). M_v <= m_v.
m_v(t) = E[N_v(t) | F_t]. Posterior expected subtree count.
M(A, C) Minimum matching distance between configurations A
and C (a bipartite assignment cost).
mu_t Posterior counting measure on Y. Total mass k.
mu^-, mu^+ Filtered and drifted posterior measures just before
and just after observing the request at time t.
nu Mover's law. nu <= mu^-, nu(Y) = 1.
N_v(t) Random number of hidden servers at leaves below v.
N_rnd = E sum_t sum_{v != root} r_{|v|-1} |Delta n_v|.
Total integer tree movement after rounding.
OPT, OPT_s Offline optimum from starting tuple s.
p_{va}(t) Pr[N_v(t) < a | F_t]. Nonincreasing in a.
p_v^circ(t) Parked mass q_v - sum_{i child of v} q_i.
P = E sum_t sum_a d_T(xi_{t-1}(X_{t-1}^a), xi_t(X_t^a)).
Expected comparator movement on the tree.
q_v(t) Fractional tree allocation at vertex v. Root holds k.
Q = E[OPT] on the input law. The budget for all budgets.
r_j = r_0 tau^{-j}, j = 0, ..., J. Scales of the tree.
R Constant in episode amplification:
floor(k diam(Y) / delta) + 1.
s, s_i Starting tuple and its entries (i = 1, ..., k).
S, D, b, d Core and flex amounts held at tree vertices, plus
various absolute tolerances.
sigma Request sequence.
tau Large absolute constant. "Separation ratio" of the
tree. >= 22 in Section 15 (rounding), >= 2 elsewhere.
T_anchor = E sum_{t,j,lambda} r_j b_{t,j,lambda} 1_{E}.
T The fixed prefix tree (Section 10). In Section 15
the L1 change term sum_i |a_i - b_i| of the rounding
lemma is ALSO called T; the context disambiguates.
u Either the tuple with distinct entries in transfer
(Section 16.5), or u = U/A in the near-dominant case
(Section 11.13).
V = E sum_t sum_{v != root} r_{|v|-1} |Delta q_v|.
Expected fractional tree movement.
w_i Side tracker coordinates in the near-dominant case.
Z The chosen optimal hidden labelled service.
z A site vector in the pilot potential.
Z_r Feasibility set of the pilot at scale r:
0 <= z_s, capacity constraint, separation constraint.
TERMS:
Allocator. The q_v(t) construction of Section 11.
Anchor. The point in Y representing a tree vertex's
current label. Any member of that label's cell
is within 20 r_j of the anchor.
Balanced rounding. n_v in {floor(q_v), ceil(q_v)} with
E[n_v | F_t] = q_v.
Cell. The set of points of Y sharing a given level-j
label.
Chronological roster. Ordered list of insertion events with
ages and lifetimes, used to label points of Y.
Dominant child. At a vertex, the unique child holding more than
84% of the mass (when such exists).
Drift. Change due to the underlying object moving at
step t, not merely due to information.
Filtering. Change due to the filtration growing from F_{t-1}
to F_t (information, not motion).
Heavy ball. A ball at the current level whose inner mass is
comparable to its outer mass, kept by the map.
HST. Hierarchies of Separated Trees. The prefix tree
of Section 10, with tau-separated levels.
Lazy simulation. The straight-line car-following lemma of
Section 8.
Parked mass. q_v - sum_children q_i, at vertex v.
Pilot potential. L_r(mu, g) of Section 12. A compact potential
that pays for partition edits in one logarithm.
Posterior. Distribution of Z given the observed prefix.
Rank function. The convex l^beta of Section 11.
Side. Any child of a vertex other than its dominant
child.
Simplex tracker. The alpha update rule of Section 11.11.
Strong laziness. A strategy that does nothing when the request
is already covered and otherwise moves exactly
one server.
Tier. A lifetime-based ball structure, indexed by h in
{1, 2, 4, ...}.
Witness. A point of Y whose leaf lies below a given tree
vertex v. Used to define anchors and masses.
------------------------------------------------------------------------
20. A HOW-TO-READ-THE-PAPER MAP
------------------------------------------------------------------------
The paper is long. Reading order by purpose:
20.1 First impression (30 minutes).
- Section 5 (main theorem, plain English) - the claim.
- Section 4 (history) - why anyone cares.
- This document's Sections 5, 6, 17 - the whole story.
- Stop.
20.2 High-school mathematical reader (a few hours).
- Section 1 (the game).
- Section 2 (competitive ratio).
- Section 3 (randomization and paging).
- Section 7 (notation: M(A,C), strong laziness, ell, scales).
- Section 8 (lazy simulation. The proof is easy and beautiful).
- Section 10 (the tree, only lightly).
- Section 17 (the money chain).
- The glossary and this map.
- SKIP sections 11-16 on first read. Skim on second.
20.3 Algorithm designer (a few days).
- Everything in 20.2.
- Section 11 in detail (allocation).
- Section 12 in detail (pilot potential).
- Section 13 in detail (partitions).
- Section 15 in detail (rounding).
- Section 16 (transfer).
- Then Section 17 to see how it fits.
Focus on:
- The picture of l^beta: convex, decreasing, linear on [0, p_*],
vanishes at s_*.
- The simplex tracker argument: feasibility + the payment
identity. Nothing else about it matters.
- The pilot potential as the one new trick that compresses a
scale sum into one logarithm.
- The BALL-MASS TELESCOPE (Section 9.6), the small lemma that
converts everything into a single log.
20.4 Probabilist / proof hound (weeks).
- Sections 9 and 12 carefully. Two pillars of stochastic
accounting.
- Section 11.5-11.9. Rank-drift + rank-tracking lemmas; all the
potentials live here.
- Sections 13.5-13.7 (the two telescopes) and 14.7 (pointwise
coefficient).
- Sections 16.3 (Yao) and 16.4 (Tychonoff / compactness). The
clean steps that remove the input law and the metric
dependence.
- Re-read Section 11 once. The tracker makes much more sense
after Section 12.
20.5 High-school competition problem solver.
Look at Section 8 (lazy simulation) and Section 9 (posterior as
filtered plus drift). These are the "that is elegant" sections:
a matching argument and a conditional-expectation exercise. The
pilot potential (Section 12) is the "that is clever" section: a
variational formula that behaves smoothly under two seemingly
different kinds of update.
20.6 What to skim on a first read.
None of the sections below contains a "trust me"; each is a full
proof. On a first read you can skim the technical algebra and
come back later. These are the ones where that is worth doing:
- Section 11.11a-b (uniform denominator estimates). The three
STATEMENTS (a),(b),(c) at the top of 11.11 are what you
actually use downstream. The integration identities in 11.11a
(regular: 1 exactly; dominant: split at y = 1 into <= 3 + 1)
and the case list in 11.11b (small y_i vs tail) are mechanical
and can be skimmed on a first pass.
- Section 11.11c (simplex feasibility). One-sentence idea: if
the constraint were violated, a small mass transfer from the
violating coordinate to some other active coordinate would
strictly decrease the objective, contradicting minimality.
The full proof (11.11c) then drills into the two cases
(transfer target exists / does not); the constants are
mechanical once you accept the idea.
- Sections 13.4-13.6 (the two partition books). The three
budgets labelled (a),(b),(c) at the top of Section 13.7 are
the formal statement. Skim each budget's derivation
(heavy edits in 13.2; first-hit lemma in 13.4;
separation in 13.5; short roster in 13.6) on a first pass;
come back if you want to verify a constant.
- Section 15.2, STEP 3 (rounding repair). STEP 1-2 (clip to the
box; adjust to the prescribed total) are easy. STEP 3 is a
finite-exchange argument whose only subtlety is the two
cases (a) and (b) of the local swap. Read those carefully if
you care about the exact constant 32 T + 11 I.
A careful reader will find that each of these is a complete proof
of the exact claim it is used for downstream.
20.7 Once you have read it once.
The paper is a chain of telescopes. Every nontrivial bound is a
sum of local positive quantities that telescopes over SCALES
(not over time). Every inequality has exactly one ell (not ell^2)
because the telescopes cancel against the geometry of balls.
Mental picture: at each scale, a "ball ratio"
log(outer_mass / inner_mass) contributes. By near-nestedness of
balls at consecutive scales, these ratios sum to about log k
over all scales. That is the one fact behind the ell's.
Every lemma answers one question: how do I pay for X moving by
Y?
- X = tree allocation, Y = comparator movement. Pay ell per
unit.
- X = partition, Y = comparator's request stream. Pay ell per
unit.
- X = rounding, Y = fractional change. Pay constant ~132 per
unit.
- X = nearby point in the pilot, Y = request. Pay local log
per unit.
------------------------------------------------------------------------
END OF DOCUMENT
------------------------------------------------------------------------
If you have read this far: the main theorem is Section 5, the proof
sketch is Section 6, the money chain is Section 17, and the honest
limits are Section 18. Everything else is detail in service of those
four sections.