The Infinite Server Problem∗
Christian Coester1 , Elias Koutsoupias1 , and Philip Lazos1

arXiv:1702.08474v1 [] 27 Feb 2017

1

Department of Computer Science, University of Oxford
March 1, 2017

Abstract
We study a variant of the k-server problem, the inﬁnite server problem, in which inﬁnitely
many servers reside initially at a particular point of the metric space and serve a sequence of
requests. In the framework of competitive analysis, we show a surprisingly tight connection
between this problem and the (h, k)-server problem, in which an online algorithm with k
servers competes against an oﬄine algorithm with h servers. Speciﬁcally, we show that the
inﬁnite server problem has bounded competitive ratio if and only if the (h, k)-server problem
has bounded competitive ratio for some k = O(h). We give a lower bound of 3.146 for
the competitive ratio of the inﬁnite server problem, which implies the same lower bound
for the (h, k)-server problem even when k/h → ∞ and holds also for the line metric; the
previous known bounds were 2.4 for general metric spaces and 2 for the line. For weighted
trees and layered graphs we obtain upper bounds, although they depend on the depth. Of
particular interest is the inﬁnite server problem on the line, which we show to be equivalent
to the seemingly easier case in which all requests are in a ﬁxed bounded interval away from
the original position of the servers. This is a special case of a more general reduction from
arbitrary metric spaces to bounded subspaces. Unfortunately, classical approaches (double
coverage and generalizations, work function algorithm, balancing algorithms) fail even for
this special case.

1

Introduction

The k-server problem is a fundamental well-studied online problem [19, 16]. In this problem k
servers serve a sequence of requests. The servers reside at k points of a metric space M and
requests are simply points of M . Serving a request entails moving one of the servers to the
request. The objective is to minimize the total distance traveled by the servers. The most
interesting variant of the problem is its online version, in which the requests appear one-byone and the online algorithm must decide how to serve a request without knowing the future
requests. It is known that the deterministic k-server problem has competitive ratio between k
and 2k − 1 for every metric space with at least k + 1 distinct points [19, 18].
In this paper, we study the infinite server problem, the variant of the k-server problem in
which there are inﬁnitely many servers, all of them initially residing at a given point, the source 1 .
At ﬁrst glance it may appear that the lower bound of k for the k-server problem would imply
∗
1

Supported by the ERC Advanced Grant 321171 (ALGAME) and by EPSRC.
We first learned about this problem from Kamal Jain [14].

1

an unbounded competitive ratio for the inﬁnite server problem. But consider, for example, the
version of the k-server problem on uniform metric spaces (i. e. the distance between any two
points is 1), and observe that the inﬁnite server problem has competitive ratio 1 for this case.
The inﬁnite server problem is closely related to the (h, k)-server problem, the resource augmentation version of the k-server problem in which the online algorithm has k servers and
competes against an oﬄine algorithm for h ≤ k servers. This model is also known as weak adversaries [2, 15]. One major open question in competitive analysis is whether the (h, k)-server
problem has bounded competitive ratio when k ≫ h. Bar-Noy and Schieber (see [5, p. 175])
showed that when h = 2, the competitive ratio on the line metric is 2 for any k, and recently,
Bansal et al. [1] showed a lower bound of 2.4 for the general case k ≫ h. Here we show a,
perhaps surprising, tight connection between the inﬁnite server problem and the (h, k)-server
problem, which allows us to improve both lower bounds to 3.146.
The inﬁnite server problem is also a considerable generalization of the ski-rental problem,
since the ski-rental problem is essentially a special case of the inﬁnite server problem when the
metric space is an isosceles triangle.

1.1

Previous Work

The k-server problem was ﬁrst formulated by Manasse et al. [19], to generalize a variety of online
setting whose stepwise cost had a ‘metric’-like structure. They build on previous work by Sleator
and Tarjan [20], the genesis of competitive analysis, on the paging problem. This problem can
be easily recast as a k-server instance for the uniform metric and was already known to be
k-competitive.
Manasse et al. [19] also showed that the competitive ratio of the k-server problem is at least
k on any metric space with more than k points. They then proposed the renowned k-server
conjecture, stating that this bound is tight. This has been shown to be true for k = 2 [19] and
for several special metric spaces [6, 7, 17, 19, 20]. A stream of reﬁnements [12, 3] lead to better
competitive ratios for general metric spaces until [18] showed that a competitive ratio of 2k − 1
can be achieved on any metric space. Chasing the competitive ratio for the deterministic (and
randomized) k-server problem has been pivotal for the development of competitive analysis. For
a more in depth view on the history of the k-server problem and further related work, we refer
to [16].
In the weak adversaries setting, signiﬁcantly less is known. For the (h, k)-server problem, the
k
on uniform metrics (equivalent to the paging problem) [20] and
exact competitive ratio is k−h+1
weighted star metrics (equivalent to weighted paging) [21]. Bansal et al. [1] showed recently for
weighted trees that the competitive ratio as k/h → ∞ can be bounded by a constant depending
on the depth of the tree. On general metrics, the (h, k)-server problem is still very poorly
understood. No algorithm is known for general metrics that performs better than disabling the
k − h extra servers and using h servers only. In fact, for the line it was shown [2, 1] that the
Double Coverage Algorithm and the Work Function Algorithm – despite achieving the optimal
competitive ratio of h if k = h [6, 4] – perform strictly worse in the resource augmentation
setting than disabling the k − h extra servers and applying the same algorithm to h servers only.
For the case that h is not ﬁxed, the Work Function Algorithm was shown to be 2h-competitive
simultaneously against any number h ≤ k of oﬄine servers [15].
In terms of lower bounds, it is known that unlike for (weighted) paging, the competitive
ratio does not converge to 1 on general metrics even as k/h → ∞. Prior to this work, the best
known lower bounds were 2 on the line [5, p. 175] and 2.4 on general metric spaces [1].
2

The closest publication to this work is by Csirik et al. [10], which studies a problem that is
essentially the special case of the inﬁnite server problem on the uniform metric space augmented
by a far away source. It is cast as a paging problem where new cache slots can be bought at a
ﬁxed price per unit and gives matching upper and lower bounds of ≈ 3.146 on the competitive
ratio.

1.2

Our Results

Our main result is an equivalence theorem between the inﬁnite server problem and the (h, k)server problem, presented in Section 2. It states that the inﬁnite server problem is competitive
on every metric space if and only if the (h, k)-server problem is O(1)-competitive on every metric
space as k/h → ∞. We show further that it is not even necessary to let k/h converge to inﬁnity
because in the positive case, there must also exist some k = O(h) for which the latter is true.
The theorem holds also if “every metric space” is replaced by “the real line”.
In Section 3 we present upper and lower bounds on the competitive ratio of the inﬁnite
server problem on a variety of metric spaces. Extending the work in [10], we present a tight
lower bound for non-discrete spaces, which is then turned into a 3.146 lower bound for the (h, k)
setting. To our knowledge, this is the largest bound on the weak adversaries setting for any
metric space, as k/h → ∞. We show how recent work by Bansal et al. [1] can be adapted to
give an upper bound on the competitive ratio of the inﬁnite server problem on bounded-depth
weighted trees. We also consider layered graph metrics, which are equivalent (up to a factor of
2) to general graph metrics. We have not settled the case for their competitive ratio, but we
present a natural algorithm with tight analysis and pose challenges for further research. The
main open question is whether there exists a metric space on which the inﬁnite server problem
is not competitive.
In Section 4 we show how a variety of known algorithms such as the work function and
balancing algorithms fail for the inﬁnite server problem, even on the real line. We focus in
particular on a class of speed-adjusted variants of the well-known double coverage algorithm.
Finally, we present a useful reduction from arbitrary metric spaces to bounded subspaces in
Section 5. In particular, the inﬁnite server problem on the line is competitive if and only if it is
competitive for the special case where requests are restricted to some bounded interval further
away from the source.

1.3

Preliminaries

Let M = (M, d) be a metric space and let s be a point of M . In the infinite server problem on
(M, s), an unbounded number of servers starts at point s and serves a ﬁnite sequence σ = (σ0 =
s, σ1 , σ2 , . . . , σm ) of requests σi ∈ M . Serving a request entails moving one of the servers to it.
The goal is to minimize the total distance traveled by the servers.
We drop s in the notation if the location of the source is not relevant or understood. We
refer to the action of moving a server from the source to another point as spawning. Throughout
this work we use the letter d for the metric associated with the metric space.
In the online setting, the requests are revealed one by one and need to be served immediately
without knowledge of future requests. All algorithms considered in this paper are deterministic.
An algorithm is called lazy if it moves only one server to serve a request at an unoccupied point
and moves no server if the requested point is already covered. An algorithm is called local [9] if
it moves a server from a to b only if there is no server at some other point c on a shortest path
3

from a to b, i. e. with d(a, b) = d(a, c) + d(c, b). It is easy to see that any algorithm can be turned
into a lazy and local algorithm without increasing its cost (i. e. the total distance traveled by all
servers).
For an algorithm ALG, we denote by ALG(σ) its cost on the request sequence σ. Similarly,
we write OPT(σ) for the optimal (oﬄine) cost.
An online algorithm ALG is ρ-competitive for ρ ≥ 1 if ALG(σ) ≤ ρOPT(σ) + c for all σ,
where c is a constant independent of σ. The competitive ratio of an algorithm is the inﬁmum
of all such ρ. We say that an algorithm is competitive if it is ρ-competitive for some ρ. We also
call an online problem itself (ρ-)competitive if it admits such an algorithm. If the additive term
c in the deﬁnition is 0, then the algorithm is also called strictly ρ-competitive [11].
The (h, k)-server problem on M is deﬁned like the inﬁnite server problem except that the
number of servers is k for the online algorithm and h for the optimal (oﬄine) algorithm against
whom it is compared in the deﬁnition of competitiveness. For this problem, the servers are not
required to start at the same point, although a diﬀerent initial conﬁguration would only aﬀect
the additive term c. The problem is interesting only when k ≥ h. The case h = k is the standard
k-server problem and the case k ≥ h is known as the weak adversaries model. One major open
problem is determine the competitive ratio of the (h, k)-server problem as k tends to inﬁnity.
We will sometimes write OPTh and OPT∞ for the optimal oﬄine algorithm, where the index
speciﬁes the number of servers available.
The following two propositions will be useful later in the paper.
Proposition 1. If for every metric space there exists a competitive algorithm for the infinite
server problem, then there exists a universal competitive ratio ρ such that the infinite server
problem is strictly ρ-competitive on every metric space.
Proof. We ﬁrst show the existence of ρ such that the inﬁnite server problem is ρ-competitive
(strictly or not) on every metric space. Suppose such ρ does not exist, then for every n ∈ N we
can ﬁnd a metric space Mn containing some point sn such that the inﬁnite server problem on
(Mn , sn ) is not n-competitive. Consider the metric space obtained by taking the disjoint union
of all spaces Mn and gluing all the points sn together. The inﬁnite server problem would not be
competitive on this metric space, in contradiction to the assumption.
Analogously we can also ﬁnd a universal constant c that works for all metric spaces as
additive constant in the deﬁnition of ρ-competitiveness. A scaling argument shows that also
c = 0 works.
With a very similar argument we get:
Proposition 2. Let k = k(h) be a function of h. Suppose that for every metric space M and for
all h there exists an O(1)-competitive algorithm for the (h, k)-server problem on M . Then there
exists a universal competitive ratio ρ such that the (h, k)-server problem is strictly ρ-competitive
on every metric space if all servers start at the same point.

2

Equivalence of Infinite Servers and Weak Adversaries

The main result of this section is the following tight connection between the inﬁnite server
problem and the weak adversaries model.
Theorem 3. The following are equivalent:
4

(a) The infinite server problem is competitive.
(b) The (h, k)-server problem is O(1)-competitive as k/h → ∞.
(c) For each h there exists k = O(h) so that the (h, k)-server problem is O(1)-competitive.
The three statements above are also equivalent if we fix the metric space to be the real line.
The implication “(c) =⇒ (b)” is trivial. The proof of the equivalence theorem consists in
its core of two reductions. Theorem 4 contains the easier of the two reductions, which is from
the inﬁnite server problem to the k-server problem against weak adversaries (“(b) =⇒ (a)”).
By Propositions 1 and 2, it suﬃces to consider only strictly competitive algorithms. Theorem 5
proves essentially the inverse for general metric spaces, and Theorem 6 specializes it to the line
(“(a) =⇒ (c)”).
As a corollary of the theorem we get the non-trivial implication “(b) =⇒ (c)”, a potentially useful statement towards resolving the major open problem about weak adversaries: “Is
Statement (b) true?” This highlights the importance of the inﬁnite server problem.
Theorem 4. Fix a metric space M and consider algorithms with all servers starting at some
s ∈ M . If for every h there exists k = k(h) such that the (h, k)-server problem on M is strictly
ρ-competitive, for some constant ρ, then there exists a strictly ρ-competitive online strategy for
the infinite server problem on M .
Proof. Let ALGk(h) denote an online algorithm with k(h) servers that is strictly ρ-competitive
against an optimal algorithm OPTh for h servers, i. e.
ALGk(h) (σ) ≤ ρOPTh (σ)

(1)

for every request sequence σ. Without loss of generality, algorithm ALGk(h) is lazy.
For every request sequence σ, consider the equivalence relation ≡σ on natural numbers in
which h ≡σ h′ if and only if ALGk(h) (σ) and ALGk(h′ ) (σ) serve σ in exactly the same way (i. e. ,
make exactly the same moves). To every σ, we associate an equivalence class H(σ) of ≡σ that
satisﬁes
• H(σ) is inﬁnite,
• H(σr) ⊆ H(σ), for every request r.
This is done inductively in the length of σ (in a manner reminiscent of König’s lemma) as follows:
For the base case when σ is the empty request sequence, H(σ) = N. For the induction step,
suppose that we have deﬁned H(σ). Consider the equivalence classes of ≡σr , a reﬁnement of
the equivalence classes of ≡σ . Since there are only ﬁnitely many possible ways to serve r, they
partition H(σ) into ﬁnitely many parts. At least one of these parts is inﬁnite and we select it to
be H(σr); if there is more than one such sets, we select one arbitrarily, say the lexicographically
ﬁrst.
Given such a mapping H, we deﬁne the online algorithm ALG∞ which serves every σ in
the same way as all the online algorithms ALGk(h) for h ∈ H(σ). The second property of H
guarantees that ALG∞ is a well-deﬁned online algorithm.
By construction, ALG∞ (σ) = ALGk(h) (σ) for every h ∈ H(σ). To ﬁnish the proof, observe
that since H(σ) is inﬁnite, it contains some h greater than the length of σ, and for such an
h we have OP T∞ (σ) = OP Th (σ). Substituting these to (1), we see that ALG∞ is strictly
ρ-competitive.
5

We now show the reduction from the k-server problem against weak adversaries to the inﬁnite
server problem on general metric spaces.
Theorem 5. If the infinite server problem on general metric spaces is strictly ρ̃-competitive,
then there exists a constant ρ such that the (h, k)-server problem is ρ-competitive, for k = O(h).
In particular, for every ǫ > 0, we can take ρ = (3 + ǫ)ρ̃ and any k ≥ (1 + 1/ǫ)ρ̃h.
Proof. Fix some metric space M and a point s ∈ M . We will describe a strictly ρ-competitive
algorithm for the (h, k)-server problem on M for the case that all servers start at s. This implies
a (not necessarily strictly) ρ-competitive algorithm for any initial conﬁguration.
The idea is to simulate a strictly ρ̃-competitive inﬁnite server algorithm, but whenever it
would spawn a (k + 1)-st server, we bring all servers back to the origin and restart the algorithm.
The problem is that the overhead cost for returning the servers to the origin, may be very high.
To compensate for this, we assume that every time the servers return to the origin, they pretend
to start from a diﬀerent point further away from the origin. This motivates the following
notation:
Definition 1. Given a metric M , a point s ∈ M , and a value w ≥ 0, we will use the notation
Ms⊕w to denote the metric derived from M when we increase the distance of s from every other
point by w; we will also denote the relocated point by s ⊕ w.
Let ALG∞ denote a strictly ρ̃-competitive online algorithm for the inﬁnite server problem.
We now deﬁne an online algorithm ALGk for k servers (all starting at s). We will make use of
the notation A(σ; s) to denote the cost of algorithm A to serve the request sequence σ when all
servers start at s.
Definition 2 (ALGk derived from ALG∞ ). Algorithm ALGk runs in phases with the initial
phase being the 0th phase. At the beginning of every phase, all servers of ALGk are at s. In
every phase i, the algorithm simulates the infinite server algorithm ALG∞ , whose servers start
at s ⊕ wi for some wi ≥ 0. The parameters wi are determined online, and initially w0 = 0.
Whenever ALG∞ spawns a server from s ⊕ wi , algorithm ALGk spawns a server from s.
The phase ends just before ALG∞ spawns its (k + 1)-st server or when the request sequence
ends. In the former case, all servers of ALGk return to s to start the (i + 1)-st phase. To
determine the starting point of the simulated algorithm of the next phase, we set
wi+1 = ǫ

OPTh (σi ; s)
,
h

(2)

where σi is the sequence of requests during phase i.
Let n be the number of phases. The cost of ALGk for the requests in phase i < n is
ALG∞ (σi ; s ⊕ wi ) − kwi ; the last term is subtracted because the k servers do not have to
actually travel the distance between s ⊕ wi and s. However for the last phase no such term can
be subtracted since we do not know how many servers are spawned during the phase, and we
can only bound the cost from above by ALG∞ (σn ; s ⊕ wn ). The cost of returning the servers to
s at the end of a phase can at most double the cost during the phase.
From this, we see that the total cost of ALGk in phase i is
(
2 (ALG∞ (σi ; s ⊕ wi ) − kwi ) for i < n
costi ≤
ALG∞ (σn ; s ⊕ wn )
for i = n .
6

Since ALG∞ is strictly ρ̃-competitive, we have
ALG∞ (σi ; s ⊕ wi ) ≤ ρ̃ OPT∞ (σi ; s ⊕ wi )
≤ ρ̃ OPTh (σi ; s ⊕ wi )
≤ ρ̃ (OPTh (σi ; s) + hwi )
and substituting this in the expression for the cost, we can bound the total cost by
ALGk (σ; s) =

n
X

costi ≤ 2

i=0

=2

n−1
X

i=0
n−1
X

(ρ̃(OPTh (σi ; s) + hwi ) − kwi ) + ρ̃(OPTh (σn ; s) + hwn )
(ρ̃OPTh (σi ; s) − (k − ρ̃h)wi ) + ρ̃OPTh (σn ; s) + ρ̃hwn .

i=0

The parameters wi and k were selected so that the summation telescopes, and we are left
with
ALGk (σ; s) ≤ 2 ρ̃ OPTh (σn−1 ; s) + ρ̃ OPTh (σn ; s) + ρ̃ ǫ OPTh (σn−1 ; s)
≤ (3 + ǫ) ρ̃ OPTh (σ; s) .
The previous reduction requires the inﬁnite server problem to be competitive on every metric
space. The following variant only requires the inﬁnite server problem to be competitive on the
line.
Theorem 6. If the infinite server problem on the line is ρ-competitive, then for every h ∈ N
and ǫ > 0, the (h, k)-server problem on the line is (3 + ǫ)ρ-competitive, when k ≥ 2⌈(1 + 1/ǫ)ρh⌉.
Proof. A straightforward adaptation of the proof of the previous lemma, shows the existence of
a (3 + ǫ)ρ-competitive algorithm for the interval [0, ∞), when k ≥ 2(1 + 1/ǫ)ρh. By doubling
the number of online servers so that half of them are used in each half-line, we get a (3 + ǫ)ρcompetitive algorithm for the entire line, when k ≥ 2⌈(1 + 1/ǫ)ρh⌉.
Note that the proof assumes strictly competitive algorithms. But, by a straightforward
scaling argument, if the inﬁnite server problem on the line is ρ-competitive, then it is also
strictly ρ-competitive. This in turn implies a strictly ρ-competitive online algorithm for M0⊕w ,
since this space is isometric to the subspace {−w} ∪ (0, ∞) of the line.
In the next section we look at some particular metric spaces and give upper and lower bounds
on the competitive ratio.

3

Upper and Lower Bounds

Unlike the k-server problem, which is 1-competitive if and only if the metric spaces has at
most k points and conjectured k-competitive otherwise, the situation is more diverse for the
inﬁnite server problem. For example, on uniform metric spaces (where all distances are the
same) the problem is trivially 1-competitive even if the metric space consists of uncountably
many points. This is because an optimal strategy in this case is to spawn a server to every
requested point. More generally, this strategy achieves a ﬁnite competitive ratio on any metric
space where distances are bounded from below and above by positive constants. This suggests
7

that statements about the competitive ratio for the inﬁnite server problem cannot be as simple
as the (conjectured) dichotomy for the k-server problem, which depends only on the number
of points of the metric space. In this section we derive bounds on the competitive ratio for
particular classes of metric spaces.

3.1

Weighted Trees

We consider the inﬁnite server problem on metric spaces that can be modeled by edge-weighted
trees. The points of the metric space are the nodes of the tree, and the distance between two
nodes is the sum of edge weights along their connecting path. We choose the source of the
metric space as the root of the tree, and deﬁne the depth of the tree as the maximal number of
edges from the root to a leaf. The number of nodes can be inﬁnite (otherwise the inﬁnite server
problem is trivially 1-competitive), but we assume the depth to be ﬁnite.
An upper bound on the competitive ratio of such trees follows easily from an upper bound
for the (h, k)-server on such trees [1] and the equivalence theorem:
Theorem 7. The competitive ratio of the infinite server problem on trees of depth d is at most
O(2d · d).
Proof. Bansal et al. [1, Theorem 1.3] showed that the competitive ratio of the (h, k)-server
problem on trees of depth d is at most O(2d · d) provided that k/h is large enough. Inspection of
the proof in [1] shows that if all servers start at the root, it is in fact strictly O(2d ·d)-competitive.
Thus, Theorem 4 implies the result for the inﬁnite server problem.

3.2

Non-Discrete Spaces and Spaces with Small Infinite Subspaces

The following theorem gives a lower bound of 3.146 on the competitive ratio of the inﬁnite server
problem on any metric space containing an inﬁnite subspace of a diameter that is small compared
to the subspace’s distance from the source. For example, every non-discrete metric space has
this property (unless the source is the only non-discrete point), since non-discrete metric spaces
contain inﬁnite subspaces of arbitrarily small diameter. The theorem is a generalization of such
a lower bound established in [10] for a variant of the paging problem where cache cells can be
bought. Crucial parts of the subsequent proof are as in [10].
Theorem 8. Let M be a metric space containing an infinite subspace M0 ⊂ M of finite diameter
δ and a point s ∈ M \ M0 such that the infimum ∆ of distances between s and points in M0 is
positive. Let λ > 3.146 be the largest real solution to
λ = 2 + ln λ .

(3)

The competitive ratio of any deterministic online algorithm for the infinite server problem on
(M, s) is bounded from below by a value that converges to λ as ∆/δ → ∞. In particular, the
competitive ratio is at least λ if M \ {s} contains a non-discrete part.
Proof. By scaling the metric, we can assume that δ = 1. Let p1 , p2 , p3 , . . . be inﬁnitely many
distinct points in M0 .
Fix some lazy deterministic online algorithm ALG. We consider the request sequence that
always requests the point pi with i minimal such that pi is not occupied by a server of ALG.
We call a move of a server between two points in M0 local (i. e. every move that does not spawn
8

is local). Let fj be the cumulative cost of local moves incurred to ALG until it spawns its jth
server. Let σk be this request sequence that is stopped right after ALG spawns its kth server,
for some large k. The total online cost is
ALG(σk ) ≥ k∆ + fk .

(4)

Let h = ⌈k/λ⌉. We consider several oﬄine algorithms that start behaving the same way, so
we think of it as one algorithm initially that is forked into several algorithms later. The oﬄine
algorithms make use of only h servers and they begin by spawning them to the points p1 , . . . , ph .
They do not need to move any servers until ALG spawns its hth server. Whenever ALG spawns
its jth server for some j ≥ h, every oﬄine algorithm is forked to h distinct algorithms: Each of
them moves a diﬀerent server to pj+1 (to prepare for the next request, which will be at pj+1 ).
We will keep the invariant that each oﬄine algorithm already has a server at the next request.
To this end, whenever ALG does a local move from p to p′ , every oﬄine algorithm that does not
have a server at p moves a server from p′ to p; note that the algorithm had a server at p′ by the
invariant, and the next request will be at p.
j 
When ALG has j spawned servers (j ≥ h), the oﬄine algorithms are in h−1
diﬀerent
conﬁgurations, each of which occurs equally often among them. If ALG does a local move from
j−1
p to p′ , there are h−1
diﬀerent oﬄine conﬁgurations for which a local move is made in the
opposite
direction.
Thus,
for each local move by ALG while having j servers in total, a portion
j−h+1
j 
j−1 
of
the
oﬄine algorithms move a server in the opposite direction for the
=
/
j
h−1
h−1
same cost.
We use the average cost of all oﬄine algorithms we considered as an upper bound on the
optimal cost. The cost of spawning h servers is at most h(∆ + 1), and the average cost while
(fj+1 − fj ) + 1 (with the “+1”
ALG has j spawned servers (for j = h, . . . , k − 1) is at most j−h+1
j
coming from the move when oﬄine algorithms fork). Hence,
OPT(σk ) ≤ h(∆ + 1) + k − h +

k−1
X
j −h+1
j=h

≤ h∆ + k +

j

(fj+1 − fj ) ,

k−1
X
k−h
h−1
fh
fk −
−
fj ,
k−1
h
j(j − 1)
j=h+1

Note that fkk is bounded from above because otherwise ALG would not be competitive, and
it is bounded from below by 0. Thus, L = lim inf k→∞ fkk exists. In the following we use the
asymptotic notation o(1) for terms that disappear as k → ∞. We can choose arbitrarily large
f
values of k such that fkk = L + o(1). Since h = ⌈k/λ⌉, we have jj ≥ L + o(1) for all j ≥ h.
Pk−1
1
Moreover, j=h+1
j−1 = ln(λ) + o(1). This allows us to simplify the previous bound to


k
∆ + λ + λ − 1 − ln(λ) L + o(1)
λ

k
=
∆ + L + λ + o(1) ,
λ

OPT(σk ) ≤

where the last step uses equation (3).

9

The competitive ratio is at least
ALG(σk ) + O(1)
≥
OPT(σk )

k∆ + fk + O(1)

∆ + L + λ + o(1)
∆+L
+ o(1) .
=λ·
∆+L+λ
k
λ

The fraction in the last term tends to 1 as ∆ → ∞.
This bound is tight due to a matching upper bound in [10] that shows (translated to the
terminology of the inﬁnite server problem) that a competitive ratio of λ can be achieved on
metric spaces where all pairwise distances are 1 except that the source is at some larger distance
∆ from the other points.
The previous theorem together with the equivalence theorem also allows us to obtain a new
lower bound for the k-server problem against weak adversaries.
Corollary 9. For sufficiently large h, there is no 3.146-competitive algorithm for the (h, k)server problem on the line, even if k → ∞.
Proof. By a scaling argument it is easy to see that if the inﬁnite server problem on the line is ρcompetitive, then it is also strictly ρ-competitive. Thus, the statement follows from Theorems 4
and 8.
This improves upon both the previous best known lower bounds of 2 for this problem on the
line [5, p. 175] and 2.4 on general metric spaces [1].

3.3

Layered Graphs

A layered graph of depth D is a graph whose (potentially inﬁnitely many) nodes can be arranged
in layers 0, 1, . . . , D so that all edges run between adjacent layers and each node – except for
a single node in layer 0 – is connected to at least one node of the previous layer. The induced
metric space is the set of nodes with the distance being the minimal number of edges of a
connecting path. For the purposes of the inﬁnite server problem, the single node in layer 0 is
the source. We assume D ≥ 2 to avoid trivial cases.
Note that a connected graph is layered if and only if it is bipartite. Moreover, any graph
can be embedded into a bipartite graph by adding a new node in the middle of each edge. So
essentially, layered graphs capture all graph metrics.
Let Move Only Outwards (MOO) be some lazy and local algorithm for the inﬁnite server
problem on layered graphs that moves servers along edges only in the direction away from the
source. Not surprisingly, the competitive ratio of this simple algorithm is quite bad and we
show that it is exactly D − 1/2. Nonetheless, at least for D ≤ 3 this is actually the optimal
competitive ratio.
Theorem 10. The competitive ratio of MOO is exactly D − 21 .
Proof.
Upper bound:

10

Consider some ﬁnal conﬁguration of the algorithm. Let nj be the number of servers in the jth
layer. Then the cost of MOO is
cost =

D
X

jnj .

j=1

To obtain an upper bound on OPT, observe that every node occupied by MOO in the ﬁnal
conﬁguration must have been visited by an oﬄine server at least once. We account an oﬄine
cost of 1 for each visit of a node on layers 1, . . . , D − 2 and an oﬄine cost of 2 for each visit
of a node on layer D. This cost of 2 covers the last two edge-traversals before visiting the
layer-D-node, so this may include serving a request on layer D − 1. If nD−1 > nD , then we can
account another nD−1 − nD cost for visiting the remaining at least nD−1 − nD requested nodes
on layer D − 1. In summary,
OPT ≥

D−2
X

nj + 2nD + (nD−1 − nD )+

j=1

where (nD−1 − nD )+ := max{0, nD−1 − nD ). The upper bound on the competitive ratio follows
since
PD
cost
j=1 jnj
≤ PD−2
+
OPT
j=1 nj + 2nD + (nD−1 − nD )
PD−2
(D − 2) j=1 nj + (2D − 1)nD + (D − 1)(nD−1 − nD )+
≤
PD−2
+
j=1 nj + 2nD + (nD−1 − nD )
1
≤D− .
2
Lower bound:
Let k, n ∈ N be some large integers. We construct the following graph: Layers 0, . . . , D − 2
consist of one node each and layers D − 1 and D consist of inﬁnitely many nodes each, denoted
a0 , a1 , a2 , . . . and b0 , b1 , b2 , . . . respectively. For each i ∈ N0 , the k nodes bik , bik+1 . . . , b(i+1)k−1
are adjacent to each of the 2k nodes aik , aik+1 , a(i+2)k−1 and to no other nodes. The set of
remaining edges is uniquely determined by the fact that this is a layered graph of depth D.
The request sequence consists of n rounds 0, 1, . . . , n − 1, where each request in round i
is at a node from the list aik , aik+1 , . . . , a(i+1)k−1 , bik , bik+1 , . . . , b(i+1)k−1 . Round i starts with
requests on the nodes aik , aik+1 , . . . , a(i+1)k−1 . Then, for j = 0, . . . , k − 1, the adversary ﬁrst
requests bik+j and then requests whichever node from aik , aik+1 , . . . , a(i+1)k−1 has been left by
an MOO-server to serve the request at bik+j . Note that by deﬁnition of MOO and the graph,
the server it moves to bik+j does indeed come from aik , aik+1 , . . . , a(i+1)k−1 .
In round i, MOO ﬁrst pays k(D − 1) to move k servers to aik , aik+1 , . . . , a(i+1)k−1 and then,
for each j = 0, . . . , k − 1, it pays 1 to move to bik+j and D − 1 to spawn a new server at the group
aik , aik+1 , . . . , a(i+1)k−1 . Over n rounds this makes a total cost of n(k(D − 1) + k(1 + D − 1)) =
nk(2D − 1).
The oﬄine algorithm can serve requests as follows: The requests at aik , . . . , a(i+1)k−1 at
the beginning of round i are served by spawning if i = 0 (for cost (d − 1)k) and by sending
11

servers from b(i−1)k , . . . , bik−1 if i ≥ 1 (for cost k). The request at bik is served by spawning
a server (cost D) and the requests at bik+1 , . . . , bik+k−1 are served by sending a server from
a node in aik , . . . , a(i+1)k−1 that will not be requested any more (cost 1 each, so k − 1 per
round). Over n rounds, this adds up to an oﬄine cost of (D − 1)k + (n − 1)k + n(D + k − 1) =
2nk + (D − 2)k + n(D − 1). The ratio of online and oﬄine cost is
2D − 1
nk(2D − 1)
,
=
D−1
2nk + (D − 2)k + n(D − 1)
2 + D−2
n + k
which gets arbitrarily close to D −

1
2

for n and k large enough.

Theorem 11. The competitive ratio of the infinite server problem on layered graphs of depth
D is exactly 1.5 for D = 2, exactly 2.5 for D = 3 and at least 3 for D ≥ 4.
Proof. For D = 2, the only possibility to move a server closer to the source is from layer 2
to layer 1. But since spawning to layer 1 is at least as good, we can restrict our attention to
algorithms of the type MOO. The result follows from Theorem 10.
For D = 3, the upper bound follows from Theorem 10. It remains to show the lower bounds
for D ≥ 3.
Fix some large integers k, n ∈ N. Consider the following layered graph of depth D. For
i = 0, . . . , D − 1 there exists a node vi in layer i. The remaining nodes are deﬁned inductively
as all nodes obtained by the following two rules:
• There exist a set S0 of 2k nodes and sets AS0 and B S0 of k nodes.
• Let S be a set of 2k nodes such that AS and B S exist. Then for each S ′ ⊂ S ∪ B S of size
′
′
2k there are sets AS and B S of k nodes.
The nodes in the sets AS are in layer D − 1, the nodes in S0 and in the sets B S are in layer D.
For a node in some set AS , the set of adjacent nodes in layer D is S ∪ B S . The remaining edges
are so that this is a layered graph with the layers as speciﬁed.
For purposes of the analysis below, we further deﬁne a generation of a node as follows: The
nodes v0 , . . . , vD−1 and the nodes in S0 have generation 1. The generation of nodes in AS and
B S is the maximal generation of any node in S plus 1.
Let ALG be some online algorithm. We assume without loss of generality that ALG is lazy
and local.
The adversary chooses the following request sequence against ALG. First, request the nodes
in S0 until ALG has a server at each of them. The adversary also moves 2k servers towards
these nodes. The adversary uses only these 2k servers for the entire sequence of requests. The
remainder of the requests consists of several rounds. We will keep the invariant that at the
beginning of the ith round, the 2k adversary servers occupy a set S for which AS and B S (with
nodes of generation i + 1) exist, and the online servers occupy nodes of generation at most i.
Clearly this holds before the ﬁrst round. Let AS = {a1 , . . . , ak } and B S = {b1 , . . . , bk }.
The requests of the ith round are divided into part a and part b, consisting of steps a.1,. . . ,a.k,
b.1,. . . ,b.k that are executed in this order. Step a.j consists of the following one or two requests:
First request aj . If ALG moves a server from some b ∈ S towards aj , immediately request b.
We can assume that online servers cover AS after the end of part a (otherwise request nodes in
AS again at the end of part a until this is the case). Step b.j consists of the following two or
three requests: First request bj . Note that any path from a node of generation at most i to bj
12

contains a node in S, and from any node in S, the shortest paths to bj include the ones along the
nodes in AS . Thus, since ALG is local, it will move a server from some a ∈ AS towards bj . The
second request of step b.j is at this node a and, if ALG moves a server from some b ∈ S ∪ B S
towards a, then the step contains a third request at b.
The adversary cost per round is at most 2k + 2: For each j = 1, . . . , k, there are at least j
nodes in S that will not be requested during steps a.j, . . . , a.k, b.1, . . . , b.(k − 1). Hence, the
adversary can serve all requests of part a for cost k by moving k servers from S towards AS
whilst keeping servers at all nodes of S that will be requested during the steps b.1,. . . ,b.(k − 1).
Similarly, it can serve the steps b.1,. . . ,b.(k − 1) for cost k − 1 by moving k − 1 servers from AS
to B S . The ﬁnal step b.k of the round can be served at cost 3 using the last server in AS to
serve the requests and ﬁnish with all 2k oﬄine servers in some set S ′ ⊆ S ∪ B S .
We analyze the online cost for the cases D = 3 and D ≥ 4 separately.
If D = 3, then the cost for each step a.j is at least 2 and the cost for each step b.j is at least
3. Thus, the cost per round is at least 5k. As k goes to inﬁnity, the ratio of online and oﬄine
cost in each round converges to 2.5. As the number of rounds goes to inﬁnity, the online and
oﬄine costs before the ﬁrst round become negligible, which proves the lower bound of 2.5 for
D = 3.
For D ≥ 4, we use a potential Φ equal to the number of online servers in layer D − 1. During
step a.j, either Φ does not change and the cost is at least 2, or Φ increases by 1 and the cost
is at least 3. Thus, during step a.j we have ∆cost ≥ 2 + ∆Φ and hence during part a we have
∆cost ≥ 2k + ∆Φ. During step b.j, either Φ decreases by 1 and the cost is at least 3, or Φ
does not change and the cost is at least 4. Thus, during part b we have ∆cost ≥ 4k + ∆Φ.
In total, this adds up to ∆cost ≥ 6k + ∆Φ during the round. Over n rounds, this makes
∆cost ≥ 6nk + ∆Φ ≥ 6nk since Φ starts at 0 before the ﬁrst round and remains nonnegative.
As k and n go to inﬁnity, the ratio of our bounds on online and oﬄine cost converges to 3.
It remains an open problem to close the gap between the lower bound of 3 and the upper
bound of 3.5 for D = 4. More importantly, we are interested in the question whether an algorithm
better than MOO exists for large D, achieving a competitive ratio of less than D − 1/2 on any
layered graph of depth D. Note that if no algorithm with a competitive ratio of O(1) as D → ∞
exists, then the inﬁnite server problem on general metric spaces would not be competitive.
For large D, the lower bound of 3 is certainly not tight: Consider a layered graph where
each layer contains one node except that the bottom layer contains inﬁnitely many nodes. By
Theorem 8 (and a matching upper bound shown in [10]), the competitive ratio on this graph
converges to λ ≈ 3.146 as D → ∞.

4

Algorithms with Unbounded Competitive Ratio

We examine the performance of classical algorithms known for the k-server problem when applied
to the inﬁnite server problem. The main focus of this section is a generalization of the Double
Coverage algorithm for the line with adjusted server speeds. This idea has proved successful for
the (h, k)-server problem (and hence the inﬁnite server problem) on weighted trees [1]. However,
neither of these algorithms is competitive for the inﬁnite server problem even on the line.

13

4.1

Work Function Algorithm

The Work Function Algorithm (WFA, [8]) for the k-server problem achieves a competitive ratio
of at most 2k − 1, which is the best known upper bound for general metric spaces [18]. Given
a sequence of requests r1 , r2 , . . . and a conﬁguration C (i. e. a multiset of server positions), the
work function wt (C) is deﬁned as the minimal cost of serving the ﬁrst t requests and ending
up in conﬁguration C. If Ct−1 is the server conﬁguration before the tth request, the algorithm
moves to a conﬁguration Ct that contains rt and minimizes the quantity
wt (Ct ) + d(Ct−1 , Ct ) ,

(5)

where d(Ct−1 , Ct ) is the cost of moving from Ct−1 to Ct .
Proposition 12. The WFA is not competitive for the infinite server problem on the line.
Proof. Let the source be at 0 and let p1 , p2 , . . . be inﬁnitely many points in the interval [1, 1 + δ]
for some small δ > 0. Consider the request sequence that always requests the point pi with i
minimal such that pi is not occupied by an online server. Let σk be the preﬁx of this request
sequence until the WFA spawns its kth server. It is easy to see that the WFA spawns its kth
server only if the optimal way of serving the already seen requests is to bring k servers to the
points p1 , . . . , pk . In particular, OPT(σk ) = k + o(1) as δ → 0. Thus, the optimal cost increases
by 1 + o(1) during the period when the WFA has k spawned servers, and the same is true for the
optimal cost of an oﬄine algorithm that is restricted to using k servers only. Let costk be the
cost incurred to the WFA during this period. Due to the lower bound of k on the competitive
ratio of any k-server algorithm, costk is at least k times this increase of the optimal cost (up to
an additive error of order o(1) as δ → 0), i. e. costk ≥ k + o(1). Thus, the total cost of WFA
given the request sequence σn is at least
n−1
X

costk = Ω(n2 ).

k=1

Meanwhile, the optimal cost is OPT(σn ) = n + o(1). Letting n tend to inﬁnity we obtain an
unbounded competitive ratio.

4.2

Balance and Balance2

The algorithm Balance serves a request r by sending a server x that minimizes the quantity
Dx + d(x, r), where Dx is the cumulative distance traveled by x so far and d(x, r) is the distance
between x and r. For the k-server problem, Balance is k-competitive on metric spaces with k + 1
points [19] and for weighted paging [6]. Young showed that for weighted paging against a weak
adversary with h servers the competitive ratio of Balance is k/(k − h+ 1) [21]. On general metric
spaces however, Balance has unbounded competitive ratio, even if k = 2 [19]. It is therefore
unsurprising that it is also not competitive for the inﬁnite server problem.
Proposition 13. Balance is not competitive for the infinite server problem on the line.
Proof. Suppose all servers start at source 0 and consider the request sequence r0 , r1 , r2 , . . . , rn
where ri = 1 − iǫ. As ǫ → 0, the optimal cost tends to 1 whereas the cost of Balance tends to
n + 1. Since n can be arbitrarily high, this shows an unbounded competitive ratio.
14

The intuitive problem of Balance is that it is not greedy enough. The algorithm Balance2
by Irani and Rubinfeld [13] compensates for this weakness by giving more weight to the distance
between the server and the request: To serve request r, Balance2 sends a server x that minimizes the quantity Dx + 2d(x, r). Irani and Rubinfeld showed that, unlike Balance, Balance2 is
competitive for two servers (achieving a competitive ratio of at most 10) and they conjectured
that it is also competitive for any other ﬁnite number of servers [13].
However, for the inﬁnite server problem this algorithm is also not competitive:
Proposition 14. Balance2 is not competitive for the infinite server problem on the line.
Proof. Suppose the source is at 0 and ﬁx some small constant ǫ > 0. The request sequence
consists of several phases, starting with phase 0. Phase i consists of alternating requests at
1 − 2iǫ and 1 − (2i + 1)ǫ. We will ensure that all requests of a phase are served by the same
online server, and we call this the active server. As soon as the cumulative distance traveled by
the active server exceeds 2 − (4i + 5)ǫ, the phase ends and a new phase begins. Note that this
means that the active server of a phase will not be used to serve any request of a subsequent
phase because, by deﬁnition of Balance2, the algorithm would rather spawn a new server. Thus,
the ﬁrst request of each phase is served by spawning a new server, which becomes the active
server of that phase. While the cumulative distance of the active server is at most 2 − (4i + 5)ǫ
and since its distance from the next request of the phase is always exactly ǫ, its associated
quantity Ds + 2d(s, r) is at most 2 − (4i + 3)ǫ. Hence, Balance2 rather uses this server during
the phase instead of spawning a new server. Thus, it is indeed the active server that serves all
requests of its phase.
Let n be the number of phases and choose ǫ small enough so that all requests are in the
interval [1/2, 1]. Thus, the cost of Balance2 is Ω(n).
An oﬄine algorithm could serve all requests with two servers only that move to 1 and 1 − ǫ
initially and then back towards 1/2, always covering the two points that are requested during a
phase, resulting in an oﬄine cost of less than 3. As n goes to inﬁnity, the ratio between online
and oﬄine cost becomes arbitrarily large.

4.3

Double Coverage Variants

Perhaps more surprising than for WFA and balancing algorithms is that a class of algorithms
extending the Double Coverage (DC) algorithm [6] is also not competitive for the inﬁnite server
problem. The basic DC algorithm on the line serves each request by an adjacent server. If the
request lies between two servers, both servers move towards it at equal speed until one of them
reaches the request. A sensible extension of this algorithm seems to be to give diﬀerent speeds
to servers, so that they move away from the source faster than towards it.
We consider here only the half-line [0, ∞) with the source at the left border 0. Let xi be
the position of the ith server from the right. We use the notation xi both for its position and
for the server itself. As servers do not overtake each other, xi is the ith spawned server. Let
S = {si ≥ 1 | i ∈ N and i ≥ 2} for a monotonic (non-decreasing or non-increasing) sequence of
speeds si . The algorithm S-DC is deﬁned as follows:
• If there exist servers xi+1 and xi to the left and right of the request, move them towards
it with speeds si+1 and 1 respectively until one of the two reaches it.
• If a request does not have a server to its right, move the rightmost server to the request.
15

If si = 1 for all i, this is precisely the original DC algorithm.
We will prove that S-DC is not competitive. The intuitive reason is that servers move to
the right either too slowly or too quickly: Imagine repeatedly requesting the same n points in
some small interval away from the source, until S-DC covers all n points. One case is that S-DC
spawns too slowly and is therefore defeated by an adversary covering these n positions immediately with n servers. In the other case, the adversary will also use n servers to cover the initial
group of requests and then shift its group of servers slowly towards the source, always making
requests at the new positions of these oﬄine servers. As S-DC tries to cover the new requests, it
is tricked into spawning too many servers. Both cases lead to an unbounded competitive ratio.
The proof consists of several lemmas. The lemmas hold also for non-monotonic speeds and
we use monotonicity only to easily combine the lemmas in the end.
A useful property of S-DC is that its cost can be calculated using only the ﬁnal positions of
the servers.
Lemma 15. Let x1 ≥ x2 ≥ . .P
. be the server positions of S-DC after serving a sequence of
requests. Then the cost paid is ∞
i=1 zi xi where
z1 = 1
1
zi−1
+1+ .
zi =
si
si

(6)

(7)

Proof. The movement xi of each server can be written as xi = ri − li where ri and li are the
cumulative distances traveled by that server while moving to the right and left respectively. By
deﬁnition of S-DC, for all i we have
li =

ri+1
,
si+1

since any right move (apart from the rightmost server) is accompanied by a left move of another
server. Observe that the online cost is
cost =

∞
∞
X
X
ri+1
(ri +
)
(ri + li ) =
si+1
i=1

i=1

=

∞
X

ri +

∞
X
ri
i=2

i=1

si

= r1 +

∞
X

ri (1 +

i=2

1
).
si

(8)

Similarly,
∞
X

zi xi =

∞
X

zi (ri − li )

i=1

i=1

=

∞
X

zi ri −

i=1

i=1

= z1 r1 +

∞
X

∞
X
i=2

zi

ri+1
si+1



zi−1
ri zi −
.
si

By equating (8) and (9) term by term, we get the desired recurrence for zi .
The next lemma takes care of the case when online servers spawn too slowly.
16

(9)

Lemma 16. If the speeds in S satisfy lim inf n→∞

p
Qn
n

i=2 si

= 1 then S-DC is not competitive.

Proof. For this lower bound we have requests on n arbitrary positions in the interval [1, 2], until
S-DC covers them all.
The optimal cost is at most 2n. This can be achieved by spawning a fresh server for each
requested position.
every spawned online server we have xi ≥ 1, by Lemma 15 the online cost is cost =
PnSince for P
n
2
2
2
i=1 zi xi ≥
i=1 zi . Unraveling the recurrence we get that zi = 1 + si + si si−1 + . . . + si ·...·s2 .
Thus,
cost ≥ n +

n−i
n−1
XX
i=1 j=1

≥

f (n) n−i
XX
i=1 j=1

where

2
Qj+i

k=j+1 sk

2
Qj+i

k=j+1 sk



n
Q
f (n) =
2 + 2 log2 ni=2 si



.

(10)

≤

n
.
2

We argue
Qj+ithat for each i = 1, . . . , f (n), it holds for at least half of the values of j = 1, . . . , n − i
that k=j+1
sk ≤ 2. Indeed, suppose this were not the case for some i. Let us partition the
set J = {1, . . . , n − i} of j-values into subsets J0 , . . . , Ji−1 , where Jm contains
precisely those
Qj+i
numbers from J that are congruent to m modulo i. By assumption, we have k=j+1 sk > 2 for
at least half the values j ∈ J, so this must also be true for at least half the values j ∈ Jm for
some m. However, this would mean that
n
Y

k=2

sk ≥

Y

j+i
Y

sk > 2|Jm |/2 ≥ 2⌊

n−i
⌋/2
i

n

≥ 2 2f (n)

−1

≥

n
Y

si ,

i=2

j∈Jm k=j+1

a contradiction because the second inequality is strict.
Thus, continuing from (10) we can further bound the online cost as
cost ≥ f (n)

n − f (n)
nf (n)
≥
.
2
4

Since the optimal cost is at most 2n, the competitive ratio is at least f (n)/8. However, f (n) is
unbounded because
n
Q
=
2 + 2 log2 ni=2 si

2
n

1
p
Qn
n

+ 2 log2

i=2 si

and the denominator in the last term gets arbitrarily close to 0.
The case of servers being spawned too aggressively is handled by the following lemma.
Lemma 17. If there exists an unbounded function f (n) such that for each k ∈ N we have
Q
k+n
i=k si ≥ f (n), then S-DC is not competitive. In particular, if lim inf i→∞ si > 1 then S-DC is
not competitive.
17

Proof. Consider the following conﬁguration of online positions and requests, denoted by circles
and crosses respectively.
v1
Newly spawned server at 1 − v1 − δ
n+1
δ δ

n
δ

δ δ
Starting at 1

We start by spawning n online servers grouped tightly, with the leftmost being at distance 1
from the source and a very small gap δ between them. This is easily accomplished by repeating
several requests on those points. Afterwards, we shift this group of n servers (by means of
requests on new n + 1 points) to the left by v1 , chosen so that the n + 1 points are covered
exactly by the n old servers plus a newly spawned one, which occupies the leftmost requested
position 1 − v1 − δ.
This is repeated again and again, shifting each time the leftmost n spawned servers a new
vk to the left via multiple requests on n + 1 positions. The goal each time is to pull a new server
from the source and leave one behind forever, thus achieving an arbitrarily high competitive
ratio for S-DC variants that spawn servers too fast.
The oﬄine cost can be calculated easily. The oﬄine algorithm uses n servers to cover the
ﬁrst group of n requested points in the interval [1, 1 + nδ]. Then it adds one more server and
moves the group of n + 1 servers to the left to satisfy all of the following requests. At most, the
group of oﬄine servers will return close to the source, yielding an optimal cost of
OPT ≤ 2(n + 1)(1 + nδ) = O(n)

(11)

since δ is very small.
To bound the online cost, we need to compute the values vk ﬁrst. Let ℓki and rik denote the
cumulative distance to the left and right respectively traveled by xi during the left shift by vk
of the group xk , xk+1 , . . . , xk+n−1 . The nonzero values among these are
ℓkk = vk
k
rk+1
= vk sk+1

ℓkk+1 = vk (1 + sk+1 )
k
= vk (sk+2 + sk+1 sk+2 )
rk+2

ℓkk+2 = vk (1 + sk+2 + sk+1 sk+2 )
..
.
k
rk+n

= vk (sk+n + sk+n−1 sk+n + . . . +

k+n
Y

j=k+1

s j ) = vk

k+n
Y
X k+n

sj .

(12)

i=k+1 j=i

On the otherPhand, the new position of the server xk+n pulled from the source during these
moves is 1 − ki=1 vi − kδ. Equating this with (12) and solving for vk yields (and assuming that
18

n is even)
Pk−1
1 − i=1
vi − kδ
vk =
Pk+n Qk+n ≤
1 + i=k+1 j=i sj

n
2

1
Qk+n

j=k+ n
2

sj

≤

2
.
nf ( n2 )

We will calculate the number of repetitions before the left border of the group of servers
(just) passes 12 . If l is the number of repetitions, we have
l

1 X
2l
≤
(vk + δ) ≤
+ lδ
2
nf ( n2 )
k=1

and for suﬃciently small δ this means that
l≥

n n
f
5
2

If we do l − 1 repetitions, then each of them will pull a new server at least 1/2 away from
the source, resulting in an online cost of Ω(n) · f ( n2 ). As the oﬄine cost is O(n) and f (n) is
unbounded, the algorithm is not competitive.
Since the sequence of speeds si is monotonic and bounded from below by 1, we have either
limi→∞ si = 1, in which case Lemma 16 applies, or otherwise lim inf i→∞ si > 1 and Lemma 17
applies. In any case, the competitive ratio is unbounded:
Theorem 18. Algorithm S-DC is not competitive for any S.

5

Reduction to Bounded Spaces

In this section we show a reduction from the inﬁnite server problem on general metric spaces to
bounded subspaces. Speciﬁcally, a metric space can be partitioned into “rings” of points whose
distance from the source is between r n and r n+1 , where r > 1 is ﬁxed and n ∈ Z. We show that
if the inﬁnite server problem is strictly ρ-competitive on each ring, then it is competitive on the
entire metric space.
Theorem 19. Let M be a metric space and s ∈ M and let r > 1. For n ∈ Z let Mn =
{s} ∪ {p ∈ M | d(s, p) ∈ [r n , r n+1 )}. If for each n the infinite server problem on (Mn , s) is
strictly ρ-competitive, then on (M, s) it is strictly 4r−1
r−1 ρ-competitive.
Proof. Let ALGn be a ρ-competitive algorithm for the inﬁnite server problem on (Mn , s).
For a request sequence σ, let σn be the subsequence of requests in Mn . Let ALG be the
algorithm for (M, s) that uses diﬀerent servers for each of the subsequences σn and serves them
independently according to ALGn .
P
P
The total online cost is ALG(σ) = n ALGn (σn ) ≤ ρ n OPT(σn ). To ﬁnish the proof, it
suﬃces to show that
X
4r − 1
OPT(σn ) ≤
OPT(σ) .
(13)
r−1
n
Thus, we only need to analyze the oﬄine cost. We do this for each oﬄine server separately. Fix
some oﬄine server x. Let N0 and N1 be the minimal and maximal values of n such that x visits
19

Mn . We can assume without loss of generality (by adding virtual points to the metric space) that
whenever x moves from Mn to Mn′ for some n < n′ , it travels across points pn+1 , pn+2 , . . . , pn′
with d(s, pi ) = r i , and similarly for n > n′ .
The movements of server x can be tracked by many servers, one server xn in every set Mn
for N0 ≤ n ≤ N1 . When server x is in Mn , server xn is exactly at the same position tracking the
movement of x. When server x exits Mn at some point p at the boundary to Mn−1 or Mn+1 ,
server xn freezes at p. The movement cost of xn can be partitioned into the cost of deploying
xn at the ﬁrst point visited in Mn , the tracking cost within Mn , and the cost of of relocating xn
whenever x re-enters Mn at a location diﬀerent from the last exiting location.
The total tracking cost of all
xn P
is bounded by the distance traveled by x. The cost
P servers
N1
n ≤
n
N1 +1 /(r − 1), which is at most r
1
of deploying all servers xn is N
r
n=−∞ r = r
n=N0
r−1
times the total movement of server x, because the latter is at least r N1 .
To bound the relocating cost, say x exits Mn at p and re-enters it at p′ . Then p and p′ are at
the boundary of Mn and Mn+u for u ∈ {−1, +1}. Let b be the distance traveled by x in Mn+u
between the times when it is entered at p and when it is next exited. If this exiting is at p′ , then
the relocating cost d(p, p′ ) is at most b by the triangle inequality. Otherwise, x exits Mn+u at a
point p′′ at the boundary of Mn+u and Mn+2u . If u = 1, then d(p, p′ ) ≤ d(s, p) + d(s, p′ ) = 2r n+1
and b ≥ d(p, p′′ ) ≥ d(s, p′′ ) − d(s, p) = r n+2 − r n+1 = (r − 1)r n+1 . If u = −1, then d(p, p′ ) ≤
n
d(s, p) + d(s, p′ ) = 2r n and b ≥ d(p, p′′ ) ≥ d(s, p) − d(s, p′′ ) = r n − r n−1 = r−1
r r . In both cases,
2r
b. Thus, the total relocating cost of all servers xn is at
the relocating cost d(p, p′ ) is at most r−1
2r
most r−1 times the total distance traveled by x.
Thus, the sum of deployment, tracking and relocating cost of the servers xn is at most 4r−1
r−1
times the distance traveled by x. This shows (13), giving the statement of the theorem.
The last theorem can also be slightly generalized to the case where instead of strict ρcompetitiveness, an additive term proportional to r n is allowed. It is not diﬃcult to show the
following specialization for the line, where the premise can be weakened to require competitiveness only on a single interval:
Corollary 20. Let 0 < a < b. The infinite server problem is competitive on the line if and only
if it is competitive on ({0} ∪ [a, b], 0).
Another consequence of Theorem 19 is a reduction to spaces where the source is at a uniform
distance from all other points.
Corollary 21. Suppose there exists ρ so that the infinite server problem is strictly ρ-competitive
on any metric space where the distance from the source to any other point is the same. Then
the infinite server problem on general metric spaces is competitive.
Proof. Follows from Theorem 19 by increasing the distance from s to the other points in Mn to
r n+1 , making a multiplicative error of at most r.

6

Open Problems

The most obvious open problem is whether the inﬁnite server problem is competitive on general
metric spaces. A challenging special case is to resolve the question for the real line. Similarly,
improving the MOO algorithm and settling the question for layered graphs remains open. It
would also be interesting to ﬁnd a metric space with a competitive ratio greater than 3.146.
Another possible line of research is to consider randomized algorithms.
20

References
[1] Nikhil Bansal, Marek Eliáš, Lukasz Jeż, and Grigorios Koumoutsos. The (h, k)-server
problem on bounded depth trees. In Proceedings of the Twenty-Eighth Annual ACM-SIAM
Symposium on Discrete Algorithms, 2017, pages 1022–1037. SIAM, 2017.
[2] Nikhil Bansal, Marek Eliáš, Lukasz Jeż, Grigorios Koumoutsos, and Kirk Pruhs. Tight
bounds for double coverage against weak adversaries. In International Workshop on Approximation and Online Algorithms, pages 47–58. Springer, 2015.
[3] Yair Bartal and Eddie Grove. The harmonic k-server algorithm is competitive. Journal of
the ACM (JACM), 47(1):1–15, 2000.
[4] Yair Bartal and Elias Koutsoupias. On the competitive ratio of the work function algorithm
for the k-server problem. Theoretical Computer Science, 324(2-3):337–345, September 2004.
[5] Allan Borodin and Ran El-Yaniv. Online computation and competitive analysis. Cambridge
University Press, 2005.
[6] Marek Chrobak, Howard Karloﬀ, Tom Payne, and Sundar Vishwanathan. New results on
server problems. SIAM Journal on Discrete Mathematics, 4(2):172–181, 1991.
[7] Marek Chrobak and Lawrence L. Larmore. An optimal on-line algorithm for k servers on
trees. SIAM Journal on Computing, 20(1):144–148, 1991.
[8] Marek Chrobak and Lawrence L Larmore. The server problem and on-line games. In
On-line Algorithms, volume 7 of DIMACS Series in Discrete Mathematics and Theoretical
Computer Science. Citeseer, 1992.
[9] Ilan R. Cohen, Alon Eden, Amos Fiat, and Lukasz Jeż. Pricing online decisions: Beyond
auctions. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on discrete
algorithms, pages 73–91. SIAM, 2014.
[10] János Csirik, Csanád Imreh, John Noga, Steve S. Seiden, and Gerhard J. Woeginger. Buying
a constant competitive ratio for paging. In European Symposium on Algorithms, pages 98–
108. Springer, 2001.
[11] Yuval Emek, Pierre Fraigniaud, Amos Korman, and Adi Rosén. On the additive constant
of the k-server work function algorithm. In International Workshop on Approximation and
Online Algorithms, pages 128–134. Springer, 2009.
[12] Amos Fiat, Yuval Rabani, and Yiftach Ravid. Competitive k-server algorithms. In Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium on, pages 454–463.
IEEE, 1990.
[13] Sandy Irani and Ronitt Rubinfeld. A competitive 2-server algorithm. Information Processing Letters, 39(2):85–91, 1991.
[14] Kamal Jain. Personal Communication.
[15] Elias Koutsoupias. Weak adversaries for the k-server problem. In Foundations of Computer
Science, 1999. 40th Annual Symposium on, pages 444–449. IEEE, 1999.
21

[16] Elias Koutsoupias. The k-server problem. Computer Science Review, 3(2):105–118, 2009.
[17] Elias Koutsoupias and Christos Papadimitriou. The 2-evader problem. Information Processing Letters, 57(5):249–252, 1996.
[18] Elias Koutsoupias and Christos H. Papadimitriou. On the k-server conjecture. Journal of
the ACM (JACM), 42(5):971–983, 1995.
[19] Mark Manasse, Lyle McGeoch, and Daniel Sleator. Competitive algorithms for on-line
problems. In Proceedings of the twentieth annual ACM symposium on Theory of computing,
pages 322–333. ACM, 1988.
[20] Daniel D. Sleator and Robert E. Tarjan. Amortized eﬃciency of list update and paging
rules. Communications of the ACM, 28(2):202–208, 1985.
[21] Neal Young. The k-server dual and loose competitiveness for paging.
11(6):525–541, 1994.

22

Algorithmica,

