BIB-VERSION:: CS-TR-v2.0
ID:: CORNELLCS//TR93-1350
ENTRY:: 1993-10-14
ORGANIZATION:: Cornell University, Computer Science Department
LANGUAGE:: English
TITLE:: A Lower Bound for Two-Server Balancing Algorithms
AUTHOR:: Kleinberg, Jon M. 
DATE:: May 1993
PAGES:: 8
ABSTRACT::
We consider the class of balancing algorithms for two servers. Such 
algorithms have appeared in a number of the early papers on this problem; 
they are so named because they seek to ``balance'' the distance travelled 
evenly among the servers. In this paper, we show a universal lower bound on 
the competitive ratio of any balancing algorithm for two servers. The 
lower bound is equal to (5 + $\sqrt{7}$)/2 ($\sim$ 3.82), and consequently 
shows that no optimal on-line algorithm for two servers can be expressed as 
a balancing algorithm.
END:: CORNELLCS//TR93-1350
BODY::
A Lower Bound for Two-Server
Balancing Algorithms*
Jon M. Kleinberg
TR 93-1350
May1993
Department of Computer Science
Cornell University
Ithaca, NY 14853-7501
*This woi?? was supported in part by the Sloan Fellowship of Eva Tardos.
A Lower Bound for Two-Server Balancing
Algoritlims *
Jon M. Kleinberg
Department of Computer Science
Cornell University, Ithaca, NY 14853, U.S.A.
Abstract
We consider the class of balancing algorithms for two servers. Such
algorithms have appeared in a number of the early papers on this prob-
lem; they are so named because they seek to "balance" the distance
travelled evenly among the servers. In this paper, we show a universal
lower bound on the competitive ratio of any balancing algorithm for
two servers. The lower bound is equal to (5 + $7)/2 (N 3.82), and
consequently shows that no optimal on-line algorithm for two servers
can be expressed as a balancing algorithm.
1. Introduction
In the k-server problem, an algorithm is given a metric space M and k
mobile robots ("servers") that can occupy points in this space. A finite
request sequence a is presented to the algorithm, one request at a time.
Each request is a point in the space M; the algorithm must move one of the
servers to this point before seeing the next request. The goal is to minimize
the total distance travelled by the servers, over the entire request sequence.
If we let S(a) denote the cost incurred by the algorithm on request se-
quence a, and OPT(a) denote the minimum cost required to serve a, then
*This work was supported in part by the Sloan Fellowship of Eva Tardos.
the algorithm is said to be c-competitive if for some absolute constant P,
the quantity cS(a) --H OPT(?) is bounded by ? over all finite sequences ?.
The infimum of the set of c for which the algorithm is c-competitive is its
competitive ratio.
A number of papers have proposed "balancing" algorithms for the k-
server problem. The basic balancing algorithm works as follows: for each
server 3?, its total distance travelled is maintained in the variable D?; when a
request is made at a point r, the algorithm sends the server which minimizes
Di + rs? (for x, y E M, let xy denote the distance between them). This
rule was shown to be k-competitive for k servers when the cardinality of the
request space M is k + 1 [5], and for the "weighted-cache" problem, which
includes the paging problem as a special case [1].
However, the algorithm is not c-competitive for any c, even for two servers,
in a general metric space M. Thus it was somewhat surprising that a rule
minimizing the quantity Di + 2rs? was shown to be 10-competitive for two
servers [4]. A later construction showed that this algorithm was no better
than 6-competitive [2].
In this note, we show a new lower bound for the class of balancing algo-
rithms in general. Let f : H ?, and B1 be the server algorithm which
does nothing when the request point is already covered, and otherwise moves
the server which minimizes Di + f(rs?), where Di is the total distance trav-
elled by server i. We will describe Bj as a balancing algorithm with cost
function f. Observe that we make no restrictions whatsoever on the nature
of the function f.
Our main result is a lower bound of (5+$7)/2 (N 3.82) on the competitive
ratio of any such balancing algorithm for two servers. In view of the 2-
competitive algorithms of [5, 3], this shows that no optimal on-line 2-server
algorithm can be expressed as a decision rule Bj for any f.
2. The Lower Bound Proof
We first define some notation that will be useful in what follows. For a server
algorithm S, let F(S) denote its competitive ratio. If 5 is c-competitive for
some c, we will say it is competitive; otherwise, we write F(S) = 00. Let
A denote the optimal (off-line) server algorithm (whose cost on a is always
OPT(a)).
2
We will say that a property P of positive real numbers holds "e.f." (ev-
erywhere but in a finite interval) if 3x0Vx > x0P(x). Similarly P holds "a.l."
(for arbitrarily large reals) if Vx0?x > xoP(x). For any function f :
p E ? p > 0, say that f E y(p) if f(x) < px e.f. If for some such p, f E ?(p),
we will write p? = inf?p: f E y(p)J; p? = Co otherwise.
Finally, the behavior of Bj is ambiguous when Di + f(rsi) = Dj + f(rs?)
for i ? j, and i, j both minimize this expression. The standard convention
here is to let the adversary break the tie; in any event, none of our construc-
tions rely on such degeneracies.
For the remainder of this note, all server algorithms will be 2-server al-
gorithms.
w
Y
z
Figure 1: Metric Space M1
Lemma 1 If Bj is competitive, then f(x) > 0 e.f.
Proof. Assume by way of contradiction that f(x) < 0 a.l. and that Bj is
c-competitive for some c. Choose x0 so that f(x0) < 0 and N0 large enough
so that N0 > cxo and N0 > --Hf(x0). Since f(x) < 0 a 1 we can find an
N> N0 such that f(N) <0.
Consider metric space M1, with WX = YZ = x0, WY = XZ = N,
and the servers initially on W? X. The first request is to the point Y. If si
responds, then we request point z; since
N + f(xo) > 0 >
server ?2 will respond. At this point, Bf has paid 2N > 2cx0, while A, by
using one server to cover requests to W, X and the other to cover ? Z, need
pay only x0. Moreover, the situation is now symmetric to the beginning,
3
so we can repeat the process indefinitely, contradicting the claim the Bj is
c-competitive. Note that if ?2 responds to the first request, then
N + f(xo) > 0 > f(N) > f(N + xo),
so s? will respond to the second request, arriving at the same contradiction.
Armed with this lemma, we can prove a much stronger result, generalizing
the observation that the basic balancing algorithm is not competitive.
Lemma 2 If B1 is competitive, then pj > 1.
Proof. Assume by way of contradiction that pj < 1 and Bj is c-competitive.
We have two cases to consider: f E ?(1) and f ?
1ff E y(l), then for some x0>0,0 < f(x) < x for all x > x0. Consider
metric space M1, with WX = YZ = x0, WY = XZ = N = cx0, and the
servers initially on W? X. Suppose we request point Y and 5i responds. if
we now request point Z, then since
N + f(xo) > N >
server ?2 will respond. Moreover, this process can be continued indefinitely.
Thus B1 pays 2cx0 in each round of this sequence, while A need pay only
x0, as in the above arguments. The case in which ?2 responds to the first
request is strictly analogous.
If f ? y(l), then we can still find some y > 0 such that 0 < f(x) <
(1 + ?21c)X for all x > y. Moreover, since f ? y(l), we can find some x0> y
such that f(x0) > x0/2. Construct metric space M1 with WX = YZ = x0,
WY = XZ = cx0, put s? on W, ?2 on X, and request point Y. If ?i responds,
then we request point Z. Since f(x0) > xo/2,
cx0 + f(x0)> (c + --H21)xo = (1 + f)cxo > f(cxo),
the last inequality following since exo > y. Thus ?2 will respond. In this way,
Bf pays 2cx0 on this sequence, while A need only pay x0. Again, the case in
which ?2 responds to Y is analogous. I
4
Zj
Figure 2: Metric Space M2
Lemma 3 If pj = p> 1, then F(B1) > pi2 + 3/2.
Proof We show that for each p > 0, there exist arbitrarily long request
sequences a for which Bj(a) > (pI2 + 3/2 --H P)A(a); this will establish the
lemma. We construct a countably infinite metric M2 as follows. The "core"
of the space is a short segment XY of length d0, chosen so that pdo/2 <
f(d0) <2pdo. The sequence a is built in phases; in phase j, j = 1,2,..., all
the requests are to X, Y, and a point Zj at distance dj from both X andY.
Let a? denote the sequence up through the end of phase j.
Let Dj denote ?`j=%1 dj, and denote the sum of Dj and the total dis-
tance travelled by both on-line servers in all previous phases. We fix some
very small a> 0, to be determined below, and since pj = p, we can choose
dj such that aD3, < c(j, and f(dj) > (p --H P/2)dj. Phase j begins with the
two on-line servers sitting on X and Y. First the point Zj is requested; then
the points X and Y are requested repeatedly until the on-line server at Zj
returns to the core XY; at this point the phase comes to an end.
In this phase, one adversary server moves out to Zj and immediately
5
returns on the next request, for a cost of 2dj
covering X and Y has built up a distance
previous phases, so it must move more than
(p + 1)dj --H 2pad? --H (P/2)dj
Meanwhile, the on-line server
of no more than from all
before dj + f(dj) could possibly exceed its total distance plus f(d0) <2pdo <
2pad?, and the server at Zj is selected to return. Thus, the on-line servers
move a distance of at least
(p+3)d3 --H2pad? --H (P/2)d3
in this phase, while the adversary servers move no more than 2dj + 2aQj in
all phases up to this one. By choosing a small enough, we can ensure that
Bj(o??)			(p +3)--H2pa--H
--H			2+2a			>?p/2+3/2--HP.
Since we can continue this construction for an arbitrary number of phases,
the result follows. I
it is clear that a very similar construction involving metric space M2
shows that if pj = 00, then B1 is not competitive. The final lemma is based
on a construction in [2].
a
w
U			b
c
v
x
Y
Figure 3: Metric Space M3
Lemma 4 If pj = p> 1, then F(Bj) > 3p/(p --H 1).
6
Proof. In the style of the previous proof, we show that for each p > 0,
F(Bj) > 3p/(p--H1)--Hfl. Choose positive ? <P/2 and ? < [2(p--H1)2/(4p--H1)]S.
Now take N large enough so that f(x) < (p + ?)x for all x > N and, since
pj > p --H e, we can find a > N such that f(a)> (p --H
Consider metric space M3. Triangles UVW and XYZ have sides of length
a; the three edges crossing between the triangles have length b = ((2p +
l)/(2p --H 2) --H ?)a. Put server 81 on U and 82 on V. We place the adversary
servers on W and Z. Also, set D1 = a/2 and D2 = 0 (this can be easily
accomplished by starting one of the on-line servers from a seventh point in
the metric space).
The adversary's strategy is as follows. It requests Z, which will be served
by 82. It then requests Y, which will be served by 81, thanks to the way we
have defined the distances. At this point, D2 exceeds D1 by a/2, and the
situation is symmetric to the beginning. The optimal algorithm can use one
server to cover each triangle and hence pays a; Bj pays 2b + a, for a ratio of
2b+a =1+ 2?+1 --H 2?>			--H
a			p--H1			p--H1
Thus we need only verify that 81 will serve the request at Y This follows
because
2p+1 2p2+2p--H1+(2p+1)?--H(2p2--H2p)?
D1+f(b) = a/2+f((2? --H 2--HS)a) ? a 2(p --H 1)
which is less than or equal to
D2 +f(a) =a+b+f(a) > a
2p2+2p--H1--H(2p--H2)(?+?)
2(p--H1)
Theorem 1 For all f, F(B1) > (5 + ?4)/2.
Proof If pj < 1 or = 00, then Bj is not competitive. In the case where
1 <pj <00, Lemmas 3 and 4 imply that
F(Bj) > ma4 Jffi' 1' P!f3y
This expression is minimized at pj = 2 + $7, with a value of (5 + $7)/2. I
As noted above, we have the following interesting corollary.
7
Corollary 1 No optimal on-line 2-server algorithm can be expressed as B1
for any function f.
3. Conclusion
We have shown a non-trivial lower bound on the competitive ratio of any
2-server balancing algorithm. It would be interesting to generalize this result
to show a lower bound of ck, for some c> 1, on the competitive ratio of any
k-server balancing algorithm. Probably more interesting, however, would
be to give a non-trivial lower bound on the competitive ratio of any server
algorithm from some computationally limited class. For example, does there
exist a 2-competitive 2-server algorithm which uses only constant time or
space per request?
Finally, it is worth noting that the lower bound given here is less than the
best known upper bound of 4 on the competitive ratio of a 2-server algorithm
using constant time and space [2]. It would be interesting to determine more
precisely the best possible competitive ratio that can be achieved by a 2-
server balancing algorithm.
References
[lj M. Chrobak, H. Karloff, T. Payne, 5. Vishwanathan, "New Results on
Server Problems," SlAM J. Discrete Math., 4(1991), pp. 172--H181.
[2j M. Chrobak, L. Larmore, "On Fast Algorithms for Two Servers," J. Al-
gorithms, 12(1991), pp. 607--H614.
[3] M. Chrobak, L. Larmore, "A New Approach to the Server Problem,"
SlAM J. Discrete Math., 4(1991), pp. 323--H328.
[4] 5. Irani, R. Rubinfeld, "A Competitive 2-Server Algorithm," Information
Processing Letters, 39(1991), pp. 85--H91.
[5] M. Manasse, L. McGeoch, D. Sleator, "Competitive Algorithms for Server
Problems," J. Algorithms, 11(1990), pp. 208--H230.
8
