Dynamic beats fixed: On phase-based algorithms
for file migration∗
Marcin Bienkowski1 , Jarosław Byrka1 , and Marcin Mucha2
1
2

Institute of Computer Science, University of Wrocław, Poland
Institute of Informatics, University of Warsaw, Poland

arXiv:1609.00831v3 [cs.DS] 25 Apr 2017

Abstract
In this paper, we construct a deterministic 4-competitive algorithm for the online file migration
problem, beating the currently best 20-year old, 4.086-competitive Mtlm algorithm by Bartal
et al. (SODA 1997). Like Mtlm, our algorithm also operates in phases, but it adapts their
lengths dynamically depending on the geometry of requests seen so far. The improvement was
obtained by carefully analyzing a linear model (factor-revealing LP) of a single phase of the
algorithm. We also show that if an online algorithm operates in phases of fixed length and the
adversary is able to modify the graph between phases, no algorithm can beat the competitive
ratio of 4.086.
1998 ACM Subject Classification F.1.2 Modes of Computation: Online computation, G.1.6 Optimization: Linear programming, F.2.2 Nonnumerical Algorithms and Problems
Keywords and phrases file migration, factor-revealing linear programs, online algorithms, competitive analysis

1

Introduction

Consider the problem of managing a shared data item among sets of processors. For example,
in a distributed program running in a network, nodes want to have access to shared files,
objects or databases. Such a file can be stored in the local memory of one of the processors
and when another processor wants to access (read from or write to) this file, it has to
contact the processor holding the file. Such a transaction incurs a certain cost. Moreover,
access patterns to this file may change frequently and unpredictably, which renders any static
placement of the file inefficient. Hence, the goal is to minimize the total cost of communication
by moving the file in response to such accesses, so that the requesting processors find the file
“nearby” in the network.
The file migration problem serves as the theoretical underpinning of the application
scenario described above. The problem was coined by Black and Sleator [13] and was initially
called page migration, as the original motivation concerned managing a set of memory pages
in a multiprocessor system. There the data item was a single memory page held at a local
memory of a single processor.
Most subsequent work referred to this problem as file migration and we will stick to this
convention in this paper. The file migration problem assumes the non-uniform model, where
the shared file is much larger than a portion accessed in a single time step. This is typical
when in one step a processor wants to read a single unit of data from a file or a record from
∗

Partially supported by Polish National Science Centre grants 2016/22/E/ST6/00499 and
2015/18/E/ST6/00456. The work of M. Mucha is part of a project TOTAL that has received funding
from the European Research Council (ERC) under the European Union’s Horizon 2020 research and
innovation programme (grant agreement No 677651).
© Marcin Bienkowski, Jarosław Byrka and Marcin Mucha;
licensed under Creative Commons License CC-BY
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

A:2

Dynamic beats fixed: On phase-based algorithms for file migration

a database. On the other hand, to reduce the maintenance overhead, it is assumed that the
shared file is indivisible, and can be migrated between nodes only as a whole. This makes
the file migration much more expensive than a single access to the file. As the knowledge
of future accesses is either partial or completely non-existing, the accesses to the file can
be naturally modeled as an online problem, where the input sequence consists of processor
identifiers, which sequentially try to access pieces of the shared file.

1.1

The Model

The studied network is modeled as an edge-weighted graph or, more generally, as a metric
space (X , d) whose point set X corresponds to processors and d defines the distances between
them. There is a large indivisible file (historically called page) of size D stored at a point
of X . An input is a sequence of space points r1 , r2 , r3 , . . . denoting processors requesting
access to the file. This sequence is presented in an online manner to an algorithm. More
precisely, we assume that the time is slotted into steps numbered from 1. Let algt denote
the position of the file at the end of step t and alg0 be the initial position of the file. In
step t ≥ 1, the following happens:
1. A requesting point rt is presented to the algorithm.
2. The algorithm pays d(algt−1 , rt ) for serving the request.
3. The algorithm chooses a new position algt for the file (possibly algt = algt−1 ) and
moves the file to algt paying D · d(algt−1 , algt ).
After the t-th request, the algorithm has to make its decision (where to migrate the file)
exclusively on the basis of the sequence up to step t. To measure the performance of an online
strategy, we use the standard competitive ratio metric [14]: an online deterministic algorithm
Alg is c-competitive if there exists a constant γ, such that for any input sequence I, it
holds that CALG (I) ≤ c · COPT (I) + γ, where CALG and COPT denote the costs of Alg
and Opt (optimal offline algorithm) on I, respectively. The minimum c for which Alg is
c-competitive is called the competitive ratio of Alg.

1.2

Previous Work

The problem was stated by Black and Sleator [13], who gave 3-competitive deterministic
algorithms for uniform metrics and trees and conjectured that 3-competitive deterministic
algorithms were possible for any metric space.
Westbrook [26] constructed randomized strategies: a 3-competitive algorithm against
adaptive-online adversaries and a (1 + φ)-competitive algorithm (for D tending to infinity)
against oblivious adversaries, where φ ≈ 1.618 denotes the golden ratio. By the result
of Ben-David et al. [10] this asserted the existence of a deterministic algorithm with the
competitive ratio at most 3 · (1 + φ) ≈ 7.854.
The first explicit deterministic construction was the 7-competitive algorithm Move-ToMin (Mtm) by Awerbuch et al. [2]. Mtm operates in phases of length D, during which the
algorithm remains at a fixed position. In the last step of a phase, Mtm migrates the file to
a point that minimizes the sum of distances to all requests r1 , r2 , . . . , rD presented in the
PD
phase, i.e., to a minimizer of the function fMTM (x) = i=1 d(x, ri ).
The ratio has been subsequently improved by the algorithm Move-To-Local-Min
(Mtlm) by Bartal et al. [8]. Mtlm works similarly to Mtm, but it changes the phase
duration to c0 · D for a constant c0 , and when computing the new position for the file, it

M. Bienkowski, J. Byrka and M. Mucha

A:3

also takes the migration distance into consideration. Namely, it chooses to migrate the file
to a point that minimizes the function
fMTLM (x) = D · d(vMTLM , x) +

c0 +1
c0

Pc0 ·D
i=1

d(x, ri ) ,

where vMTLM denotes the point at which Mtlm keeps its file during the phase. The algorithm
is optimized by setting c0 ≈ 1.841 being the only positive root of the equation 3c3 − 8c − 4 = 0.
For such c, the competitive ratio of Mtlm is R0 ≈ 4.086, where R0 is the largest (real) root
of the equation R3 − 5R2 + 3R + 3 = 0. Their analysis is tight.
It is worth noting that most of the competitive ratios given above hold when D tends to
infinity. In particular, for Mtlm we assume that c0 · D is an integer and the ratio of 1 + φ of
Westbrook’s algorithm [26] is achieved only in the limit.
Better deterministic algorithms are known only for some specific graph topologies. There
are 3-competitive algorithms for uniform metrics and trees [13], and (3 + 1/D)-competitive
strategies for three-point metrics [23]. Chrobak et al. [15] showed 2 + 1/(2D)-competitive
strategies for continuous trees and products of trees, e.g., for Rn with `1 norm. Furthermore,
a (1 + φ)-competitive algorithm for Rn under any norm was also given in [15].
A straightforward lower bound of 3 for deterministic algorithms was given by Black and
Sleator [13] and later adapted to randomized algorithms against adaptive-online adversaries
by Westbrook [26]. The currently best lower bound for deterministic algorithms is due to
Matsubayashi [22], who showed a lower bound of 3 + ε that holds for any value of D, where
ε is a constant that does not depend on D. This renders the file migration problem one
of the few natural problems, where a known lower bound on the competitive ratio of any
deterministic algorithm is strictly larger than the competitive ratio of a randomized algorithm
against an adaptive-online adversary.
Finally, improved results were given for a simplified model where D = 1: the competitive
ratio for deterministic algorithms is then known to be between 3.164 and 3.414 [21].

1.3

Our Contribution

We propose a new deterministic algorithm that dynamically decides on the length of the
phase based on the geometry of requests received in the initial part of each phase. This
improves the 20-years old result of Bartal et al. [8].
The improvement was obtained by carefully analyzing a linear model (factor revealing
LP) of a single phase of the algorithm. It allowed us to identify some key tight examples
for the previous analysis, suggested a nontrivial construction of the new algorithm, and
facilitated a systematic search within the design parameter space.
More precisely, for a fixed algorithm Alg (from a relatively broad class), we create
a maximization LP with the following property: if the competitive ratio of Alg is at least R,
then so is the value of LP. A solution to the LP contains a succinct description of a metric
space along with a short description of a single-phase input, both constituting a lower bound
for Alg. Hence, the value of LP is an upper bound on Alg’s competitiveness. We discuss
the details of the LP approach in Section 4.
The way the algorithm was obtained is perhaps unintuitive. Nevertheless, the final
algorithm is an elegant construction involving only essentially integral constants. By studying
the dual solution, we managed to extract a compact, human-readable, combinatorial upper
bound based on path-packing arguments and to obtain the following result.
I Theorem 1. There exists a deterministic 4-competitive algorithm for the file migration
problem.

A:4

Dynamic beats fixed: On phase-based algorithms for file migration
Q

S

a

a

b

Figure 1 The geometries of selected tight instances for Mtlm. In both cases, the algorithm
starts at point a. In the linear instance (on the right), the requests are initially given at a and then
later at b, and the algorithm is expected to migrate the file to point b. In the bipartite instance (on
the left) the requests are given at nodes from set S and the algorithm is expected to migrate the file
to one of the nodes from set Q.

We also show that improvement of Mtlm would not be possible by just selecting different
parameters for a phase-based algorithm operating with a fixed phase length. Our construction
shows that an analysis that treats each phase separately (e.g., the one employed for Mtlm [8])
cannot give better bounds on the competitive ratio than 4.086. (A weaker lower bound of
3.847 for algorithms that use fixed phase length was given by Bartal et al. [8].)
I Theorem 2. Fix any algorithm Alg that operates in phases of fixed length. Assume
that between the phases, the adversary can arbitrarily modify the graph while keeping the
distance between the files of Opt and Alg unchanged. Then, the competitive ratio of Alg
is at least R0 (for D tending to infinity), where R0 ≈ 4.086 is the competitive ratio of
algorithm Mtlm.

1.4

Other Related Work

The file migration problem has been generalized in a few directions. When we lift the
restriction that the file can only be migrated and not copied, the resulting problem is called
file allocation [9, 2, 18]. It makes sense especially when we differentiate read and write
requests to the file; for the former, we need to contact only one replica of the file; for the
latter all copies need to be updated. The attainable competitive ratios become then worse:
the best deterministic algorithm is O(log n)-competitive [2]; the lower bound of Ω(log n)
holds even for randomized algorithms and follows by a reduction from the online Steiner tree
problem [9, 17].
The file migration problem has been also extended to accommodate memory capacity
constraints at nodes (when more than one file is used) [1, 3, 4, 6], dynamically changing
networks [4, 12], and different objective functions (e.g., minimizing congestion) [19, 25]. For
a more systematic treatment of the file migration and related problems, see surveys [7, 11].
For more applied approaches, see the survey [16] and the references therein.

2

4-Competitive Algorithm Dynamic-Local-Min

We start with an insight concerning the hard inputs for the Mtlm algorithm [8]. We identified
two classes of tight instances for Mtlm: bipartite and linear (cf. Figure 1). It can be shown
that if the algorithm knew in advance on which instance it was run, it could improve its
performance by changing the phase length. Namely, for bipartite instances a longer phase
would help the algorithm, whereas a shorter phase would be beneficial for linear instances.
To decide the length of the phase, we need to measure the level of request concentration as
compared to the distance from the current position of an algorithm to the center of requests.
Intuitively, observing that (from some time) requests are concentrated around a certain

M. Bienkowski, J. Byrka and M. Mucha

point motivates the algorithm to shorten the phase and quickly move to the “center of the
requests”. If, on the other hand, requests are scattered and the current algorithm’s position
is essentially in the middle of the observed requests, it appears reasonable to wait longer
before moving the file. This rule agrees with the desired behavior of the algorithm on linear
and bipartite instances.
Turning the above intuition into an effective phase extension rule is not trivial. We
present an algorithm based on a rule that we have extracted from an optimization process
using a natural linear model of the amortized phase-based analysis. This linear model is quite
complex and we present it in Section 4. It can be seen as an alternative (computer-based)
proof for the performance guarantee of our algorithm. Such proof technique might be
interesting on its own and useful for analyzing other online games played on metric spaces.

2.1

Notation

For succinctness, we introduce the following notions. For any two points v1 , v2 ∈ X , let
[v1 , v2 ] = D · d(v1 , v2 ). We extend this notation to sequences of points, i.e., [v1 , v2 , . . . , vj ] =
[v1 , v2 ] + [v2 , v3 ] + . . . + [vj−1 , vj ]. Moreover, if v ∈ X is a point and S ⊆ X is a multiset of
points, then
[v, S] = [S, v] = D ·

1
|S|

P

x∈S

d(v, x) ,

i.e., [v, S] is the average distance from v to a point of S times D. We extend the sequence
notation introduced above to sequences of points and multisets of points, e.g., [v, S, u, T ] =
[v, S] + [S, u] + [u, T ]. The symbol [S, T ] is not defined for multisets S, T ; we will only use
this notation for sequences that do not contain two consecutive multisets.
Observe that the sequence notation allows for easy expressing of the triangle inequality:
[v1 , v2 ] ≤ [v1 , v3 , v2 ]; we will extensively use this property. Note that the following “multiset”
version of the triangle inequality also holds: [v1 , v2 ] ≤ [v1 , S, v2 ].

2.2

Algorithm definition

We propose a new phase-based algorithm that dynamically decides on the length of the
current phase, which we call Dynamic-Local-Min (Dlm). Dlm operates in phases, but it
chooses their lengths depending on the geometry of requests seen in the initial part of the
phase. Roughly speaking, when it recognizes that the currently seen requests more closely
resemble a linear tight example for Mtlm, it ends the phase after 1.75 D steps. Otherwise,
it assumes that the presented graph is more in the flavor of the bipartite construction, and
ends the phase only after 2.25 D steps.
For any step t, we denote the position of Dlm’s file at the end of step t by dlmt and
that of Opt by opt . We identify the requests with the points where they are issued.
Assume a phase starts in step t + 1; that is, dlmt is the position of Dlm at the very
beginning of a phase. Within the phase, Dlm waits 1.75 D steps and at step t + 1.75 D, it
finds a node vg that minimizes the function
g(v) = [dlmt , v, R1 , v, R2 ] = [dlmt , v] + 2 · [v, R1 ] + [v, R2 ] ,
where R1 is the multiset of the requests from steps t + 1, . . . , t + D and R2 is the multiset of
the subsequent requests from steps t + D + 1, . . . , t + 1.75 D.
If g(vg ) ≤ 1.5 · [dlmt , R2 ], the algorithm moves its file to vg , and ends the current phase.
Intuitively, this condition corresponds to detecting if there exists a point that is substantially

A:5

A:6

Dynamic beats fixed: On phase-based algorithms for file migration

closer to the first 1.75 D requests of the phase than the current position. The condition is
constructed in a way to be conclusive for each of the possible outcomes. If indeed such point
exists, then by moving the file to this point, we get much closer to the file of Opt. If there is
no such good point, then also the optimal solution is experiencing some request related costs.
Then, we may afford to wait a little longer and meanwhile get a more accurate estimation of
the possible location of the file of Opt.
That is, if g(vg ) > 1.5 · [dlmt , R2 ], Dlm waits the next 0.5 D steps and (in step t + 2.25 D)
it moves its file to the point vh , where vh is the minimizer of the function
h(v) = [dlmt , v] + [v, R1 ] + 1.25 · [v, R2 ] + 0.75 · [v, R3 ] .
R3 is the multiset of the last 0.5 D requests from the prolonged phase (from steps t + 1.75 D +
1, . . . , t + 2.25 D). Also in this case, the next phase starts right after the file movement.
Note that the short phase consists of D requests denoted R1 followed by 0.75 D requests
denoted R2 , while the long phase consists additionally of 0.5 D requests denoted R3 . We
will say that the short phase consists of two parts, R1 and R2 , and the long phase consists
of three parts, R1 , R2 and R3 .

2.3

DLM Analysis

We start with a lower bound on Opt. The following bound is an extension of the bound
given implicitly in [8]; we present its proof for completeness in Appendix A.
I Lemma 3. Let R be a subsequence of at most 2D consecutive requests from the input
issued at steps t + 1, t + 2, . . . , t + |R|. Then, 4 · COPT (R) ≥ (2|R|/D) · [opt , R, opt+|R| ] +
(4 − 2|R|/D) · [opt , opt+|R| ].
We define a potential function at (the end of) step t as Φt = 3 · [dlmt , opt ]. It suffices to
show that in any (short or long) phase consisting of steps t + 1, t + 2, . . . , t + `, during which
requests R are given, it holds that
CALG (R) + Φt+` ≤ 4 · COPT (R) + Φt .

(1)

Theorem 1 follows immediately by summing the above bound over all phases of the input.

2.3.1

Proof for a short phase.

We consider any short phase R consisting of part R1 , spanning steps t + 1, . . . , t + D, and
part R2 , spanning steps t + D + 1, . . . , t + 1.75 D. For succinctness, we define op0 = opt ,
op1 = opt+D and op2 = opt+1.75 D . By Lemma 3 applied to R1 and R2 ,
4 · COPT (R) + Φt = 3 · [dlmt , op0 ] + 4 · COPT (R1 ) + 4 · COPT (R2 )
≥ 3 · [dlmt , op0 ] + 2 · [op0 , op1 ] + 2 · [op0 , R1 , op1 ]
1

2

1

(2)

2

+ 2.5 · [op , op ] + 1.5 · [op , R2 , op ] .
We treat the amount (2) as our budget. This is illustrated below; the coefficients are written
as edge weights.
op0

dlmt

op1

3

op2

2
2

2.5
2

R1

1.5

1.5
R2

Budget = 4 OPT
+ initial potential
(short phase case)
xxxxxxxxxxxxxxxxxxxxxx

M. Bienkowski, J. Byrka and M. Mucha

A:7

Now, we bound CALG (R) + Φt+1.75 D using the definition of Alg and the triangle inequality.
CALG (R) + Φt+1.75 D
= CALG (R1 ) + CALG (R2 ) + 3[vg , op2 ]
≤ [dlmt , R1 ] + 0.75 · [dlmt , R2 ] + [dlmt , vg ] + 3 · [vg , op2 ]
≤ [dlmt , R1 ] + 0.75 · [dlmt , R2 ] + [dlmt , vg ] + 2 · [vg , R1 , op2 ] + [vg , R2 , op2 ]
= [dlmt , R1 ] + 0.75 · [dlmt , R2 ] + 2 · [op2 , R1 ] + [op2 , R2 ]
+ [dlmt , vg ] + 2 · [vg , R1 ] + [vg , R2 ]
= [dlmt , R1 ] + 0.75 · [dlmt , R2 ] + 2 · [op2 , R1 ] + [op2 , R2 ] + g(vg ) .

(3)

The first four summands of (3) can be bounded as
[dlmt ,R1 ] + 0.75 · [dlmt , R2 ] + 2 · [op2 , R1 ] + [op2 , R2 ]
0

0

(4)

1

2

1

2

≤ [dlmt , op , R1 ] + 0.75 · [dlmt , op , op , R2 ] + 2 · [op , op , R1 ] + [op , R2 ] ,
and their total weights in the final expression are depicted below.
op0

dlmt

op1

1.75

op2

0.75
1

DLM cost
+ final potential
(part 1, short phase)

2
2

0.75

R1

1

xxxxxxxxxxxxxxxxxxxxxx

R2

For the last summand of (3), g(vg ), we use the fact that vg is a minimizer of the function g
(and hence g(vg ) ≤ g(op0 )), and the property of the short phase (g(vg ) ≤ 1.5 · [dlmt , R2 ]).
Therefore,
g(vg ) ≤ 0.5 · g(op0 ) + 0.75 · [dlmt , R2 ]
≤ 0.5 · [dlmt , op0 , R1 , op0 , R2 ] + 0.75 · [dlmt , R2 ]
0

0

1

2

(5)
0

1

≤ 0.5 · [dlmt , op , R1 , op , op , op , R2 ] + 0.75 · [dlmt , op , op , R2 ] .
op0

dlmt

op1

1.25

op2

1.25
1

0.5
0.75

R1

0.5
R2

DLM cost
+ final potential
(part 2, short phase)
xxxxxxxxxxxxxxxxxxxxxx

By combining (3), (4) and (5) (or simply adding the edge coefficients on the last two figures)
we observe that the budget ((2), i.e., the edge coefficients on the first figure) is not exceeded.
This implies 4-competitiveness, i.e., that (1) holds for any short phase.

2.3.2

Proof for a long phase.

We consider any long phase R consisting of part R1 , spanning steps t + 1, . . . , t + D; part R2 ,
spanning steps t + D + 1, . . . , t + 1.75 · D; and part R3 , spanning steps t + 1.75 · D + 1, . . . , t +
2.25 · D. Similarly to the proof for a short phase, we define op0 = opt , op1 = opt+D ,
op2 = opt+1.75 D , and op3 = opt+2.25 D . We emphasize that the positions of Opt in a long
and a short phase can be completely different.

A:8

Dynamic beats fixed: On phase-based algorithms for file migration

By Lemma 3, we obtain a bound very similar to that for a short phase; again, we treat it
as a budget and depict its coefficients as edge weights.
4 · COPT (R) + Φt = 3 · [dlmt , op0 ] + 4 · COPT (R1 ) + 4 · COPT (R2 ) + 4 · COPT (R3 )
≥ 3 · [dlmt , op0 ] + 2 · [op0 , op1 ] + 2 · [op0 , R1 , op1 ]
1

2

1

(6)

2

+ 2.5 · [op , op ] + 1.5 · [op , R2 , op ]
+ 3 · [op2 , op3 ] + [op2 , R3 , op2 ] .
op0

dlmt

op1

3

op2

2
2

op3

2.5
2

1.5

1.5

R1

Budget = 4 OPT
+ initial potential
(long phase case)

3
1

R2

1

xxxxxxxxxxxxxxxxxxxxxx

R3

Now, we bound CALG (R) + Φt+2.25 D , using the definition of Alg and the triangle inequality.
CALG (R) + Φt+2.25 D
= CALG (R1 ) + CALG (R2 ) + CALG (R3 ) + 3 · [vh , op3 ]
= [dlmt , R1 ] + 0.75 · [dlmt , R2 ] + 0.5 · [dlmt , R3 ] + [dlmt , vh ] + 3 · [vh , op3 ]
≤ [dlmt , R1 ] + 0.75 · [dlmt , R2 ] + 0.5 · [dlmt , R3 ] + [dlmt , vh ]
+ [vh , R1 , op3 ] + 1.25 · [vh , R2 , op3 ] + 0.75 · [vh , R3 , op3 ]
= [dlmt , R1 ] + 0.75 · [dlmt , R2 ] + 0.5 · [dlmt , R3 ]
3

3

(7)

3

+ [op , R1 ] + 1.25 · [op , R2 ] + 0.75 · [op , R3 ] + h(vh ) .
Since Dlm has not migrated the file after the first two parts, g(v) ≥ 1.5 · [dlmt , R2 ] for
any node v. Therefore 0.75 · [dlmt , R2 ] ≤ 0.5 · g(op0 ) = 0.5 · [dlmt , op0 , R1 , op0 , R2 ] ≤
0.5 · [dlmt , op0 , R1 , op0 , op1 , R2 ]. Using this and the triangle inequality, the first three
summands of (7) can be bounded and depicted as follows:
[dlmt ,R1 ] + 0.75 · [dlmt , R2 ] + 0.5 · [dlmt , R3 ]
≤ [dlmt , op0 , R1 ] + 0.5 · [dlmt , op0 , R1 , op0 , op1 , R2 ]
0

1

(8)

2

+ 0.5 · [dlmt , op , op , op , R3 ] .
op0

dlmt

op1

2

op2

1

op3
DLM cost
+ final potential
(part1, long phase)

0.5

2

0.5
R1

0.5
R2

xxxxxxxxxxxxxxxxxxxxxx

R3

The next three summands of (7) can be also bounded appropriately:
[op3 ,R1 ] + 1.25 · [op3 , R2 ] + 0.75 · [op3 , R3 ]
≤ [op3 , op2 , op1 , R1 ] + 1.25 · [op3 , op2 , R2 ] + 0.75 · [op3 , R3 ] .
dlmt

op0

op1

op2
1

1
R1

op3
2.25

1.25
R2

(9)

0.75
R3

DLM cost
+ final potential
(part 2, long phase)
xxxxxxxxxxxxxxxxxxxxxx

M. Bienkowski, J. Byrka and M. Mucha

A:9

Lastly, for bounding h(vh ), we use the fact that vh is a minimizer of h, and hence
h(vh ) ≤ h(op1 )
= [op1 , dlmt ] + [op1 , R1 ] + 1.25 · [op1 , R2 ] + 0.75 · [op1 , R3 ]
≤ [op1 , op0 , dlmt ] + [op1 , R1 ] + [op1 , R2 ] + 0.25 · [op1 , op2 , R2 ]
1

2

1

2

(10)

3

+ 0.5 · [op , op , R3 ] + 0.25 · [op , op , op , R3 ] .
Note that in (10) we split some of the paths and choose the longer ones, so that the budgets
on edges are not violated. Bound (10) is depicted on the figure below.
op0

dlmt
1

op1

op2

1
1
R1

op3

1
1

0.25
0.25

R2

0.5

0.25
R3

DLM cost
+ final potential
(part 3, long phase)
xxxxxxxxxxxxxxxxxxxxxx

By combining (7), (8), (9) and (10) (or simply adding edge coefficients on the last three
figures), we observe that the budget ((6), i.e., the edge coefficients on the first figure) is
not exceeded. This implies 4-competitiveness, i.e., that (1) holds for any long phase and
concludes the proof of Theorem 1.

3

Lower Bound for Phase-Based Algorithms

A fixed-phase algorithm chooses phase length c · D and after every c · D requests it makes
a migration decision solely on the basis of its current position and the last c · D requests.
We now proceed to argue that no fixed-phase algorithm Alg can beat the competitive ratio
R0 ≈ 4.086 achieved by Mtlm [8] (cf. Theorem 2). As already stated in the introduction,
to ensure that the algorithm cannot base its choices on the previous phases, we will give
the adversary an additional power: it may modify the graph between the phases of Alg,
as long as the distance between nodes keeping the files of Alg and Opt (valg and vopt ,
respectively) is preserved. We emphasize that the analysis of Mtlm [8] essentially uses this
model: each phase is analyzed completely separately from others. The full proof is presented
in Appendix B; here we informally highlight its key ideas.
The adversarial construction consists of many epochs, each consisting of some number
of phases. At the beginning and at the end of an epoch, Alg and Opt keep their files at
the same node. We define three adversarial strategies, called plays: linear, bipartite, and
finishing. Each play consists of one or more phases. A prerequisite for each given play is
a particular distance between valg and vopt . Each play will have some properties: it will
incur some cost on Alg and Opt and will end with valg and vopt in a specific distance.
In the first phase of an epoch, when initially valg = vopt , the adversary uses the linear
play (the generated graph is a single edge of length 1), so that at the end of the phase,
d(valg , vopt ) = 1. For such phase P , we have CALG (P ) ≥ R0 · COPT (P ) − (1/(1 − 2α)) · D,
where α = 1/(R0 − 1). Note that in this phase alone, the adversary does not enforce the
desired competitive ratio of R0 , but it increases the distance between vopt and valg .
In each of the next L phases, the adversary employs the bipartite play; the graph used
corresponds to a tight bipartite example for Mtlm, cf. Figure 1). Let f be the value of
d(valg , vopt ) at the beginning of a phase. If the algorithm plays well, then at the end of
the phase this distance decreases to 2α · f . Furthermore, neglecting lower order terms,
for such phase P , it holds that CALG (P ) ≥ R0 · COPT (P ) + f · D, i.e., the inequality
CALG (P ) ≥ R0 · COPT (P ) holds with the slack f · D. The sum of these slacks over L phases

A:10

Dynamic beats fixed: On phase-based algorithms for file migration

PL−1
is i=0 (2α)i · D, which tends to (1/(1 − 2α)) · D when L grows. Hence, after one linear
and L bipartite phases (for a large L and neglecting lower order terms again), the cost paid
by Alg is at least R0 times the cost paid by Opt and the distance between their files is
negligible.
Finally, to decrease the distance between valg and vopt to zero, the adversary uses a third
type of play, the finishing one. This play incurs a negligible cost and it forces the positions
of Alg and Opt files to coincide, which ends an epoch.

4

Linear Program for File Migration

In this section, we present a linear programming model for the analysis of both algorithm
Mtlm by Bartal et al. [8] and our algorithm Dlm.

4.1

LP analysis of MTLM-like algorithms

In our approach, we analyze any Mtlm-like algorithm Alg. We use our notion of distances
from Section 2.1. Alg will be a variant of Mtlm parameterized with two values β and δ.
The length of its phase is δ · D and the initial point of Alg is denoted by A0 . We denote
the set of requests within a phase by R. At the end of a phase, Alg migrates the file to
a point A1 that minimizes the function
f (x) = [A0 , x] + β · [x, R] .
As in the amortized analysis of the algorithm Mtlm [8], we will use a potential function
equal to φ times the distance between the files of Alg and Opt, where φ is a parameter
used in the analysis. We let O0 and O1 denote the initial and final position of Opt during
the studied phase, respectively. Then, the amortized cost of Alg in a single phase is
CALG = δ · [A0 , R] + [A0 , A1 ] + φ([A1 , O1 ] − [A0 , O0 ]).
The following factor-revealing LP mimics the proof given in [8]. Namely, it encodes
inequalities that are true for any phase and a graph on which Alg can be run. Its goal is to
maximize the ratio between CALG and COPT : as an instance can be scaled, we set COPT = 1
and we maximize CALG . Let V = {A0 , A1 , O0 , O1 } and V 0 = V ∪ {R}.
maximize CALG
subject to:
CALG = δ · [A0 , R] + [A0 , A1 ] + φ · ([A1 , O1 ] − [A0 , O0 ])
COPT = 1
req
move
COPT = COPT
+ COPT
move
COPT
≥ [O0 , O1 ]
req
move
2 · COPT
+ δ · COPT
≥ δ · [O0 , R] + δ · [O1 , R]

f (A1 ) ≤ f (v)

for all v ∈ V

0 ≤ [v1 , v3 ] ≤ [v1 , v2 ] + [v2 , v3 ]

for all v1 , v2 , v3 ∈ V 0

As R is a set of requests, it does not necessarily correspond to a single point in the
studied metric. Nevertheless, our notion of average distances (i.e., [v1 , v2 ]) allows us to write
the triangle inequalities for any pair of objects from set V ∪ {R}.
req
move
In the LP above, COPT
, COPT
denote the cost of Opt for serving the request and the
req
move
cost of Opt for migrating the file, respectively. The inequality 2 · COPT
+ δ · COPT
≥
δ · [O0 , R] + δ · [O1 , R] is a counterpart of the relation guaranteed by Lemma 3.

M. Bienkowski, J. Byrka and M. Mucha

A:11

For any choice of parameters β, δ, and φ, the LP above finds an instance that maximizes
the competitive ratio of Alg. Note that such instance is not necessarily a certificate that
Alg indeed performs poorly: in particular, inequalities that lower-bound the cost of Opt
might not be tight. However, the opposite is true: if the value of CALG returned by the LP
is ξ, then for any possible instance the ratio is at most ξ.
Let c0 = 1.841 be the phase length of Mtlm. Setting δ = c0 and β = φ = 1 + c0 yields
that the optimal value of the LP is R0 ≈ 4.086, which can be interpreted as a numerical
counterpart of the original analysis in [8]. To obtain a formal mathematical proof, one may
take a dual solution to the LP. It gives the coefficients that multiplied by the corresponding
LP inequalities and summed over all inequalities yield a proof that the amortized cost of
Mtlm in any phase is at most R0 times the cost of Opt. Summed over all phases, this
implies that Mtlm is R0 -competitive.
Among other advantages, this approach allows us to numerically find the instances that
are tight for the current analysis (cf. Section 2 and Figure 1): linear and bipartite instances
can be obtained this way.

4.2

LP analysis of DLM-like algorithms

Now we show how to adapt the LP from the previous section to analyze Dlm-type algorithms.
Recall that after 1.75 D requests, Dlm evaluates the geometry of the so-far-received requests
and decides whether to continue this phase or not. Although the final parameters of Dlm are
elegant numbers (multiplicities of 1/4), they were obtained by a tedious optimization process
using the LP we present below. Furthermore, the LP below does not give us an explicit rule
for continuing the phase; it only tells that Dlm is successful either in a short or in a long
phase.
Recall that in a phase, Dlm considers three groups of consecutive δi · D requests: R1 ,
R2 , and R3 , where δ1 , δ2 , and δ3 are parameters of Dlm. First, assume that Dlm always
processes three parts and afterwards it moves the file to a point A3 that minimizes the
function
h(x) = [A0 , x] + β1 · [x, R1 ] + β2 · [x, R2 ] + β3 · [x, R3 ] ,
where βi are parameters that we choose later. We denote the strategy of an optimal algorithm
by OptL (short for Opt-Long). Let O0L , O1L , O2L and O3L denote the trajectory of OptL
(O0L is the initial position of the OptL’s file at the beginning of the phase, and OiL is its
position right after the i-th part of the phase). Analogously to the previous section, we
obtain the following LP.
maximize CALGL
subject to:
CALGL = [A0 , A3 ] +

P

i=1,2,3 δi

· [A0 , Ri ] + φ · ([A3 , O3L ] − [A0 , O0L ])

COPTL = 1
P
req
move
COPTL = i=1,2,3 (COPTL
(i) + COPTL
(i))
move
L
COPTL
(i) ≥ [Oi−1
, OiL ]

for i = 1, 2, 3

req
move
L
2 · COPTL
(i) + δ · COPTL
(i) ≥ δi · [Oi−1
, Ri ] + δi · [OiL , Ri ]

for i = 1, 2, 3

h(A3 ) ≤ h(v)

for all v ∈ V

0 ≤ [v1 , v3 ] ≤ [v1 , v2 ] + [v2 , v3 ]

for all v1 , v2 , v3 ∈ V 0

This time V = {A0 , A3 , O0L , O1L , O2L , O3L } and V 0 = V ∪ {R1 , R2 , R3 }.

A:12

Dynamic beats fixed: On phase-based algorithms for file migration

We note that such parameterization alone does not improve the competitive ratio, i.e., for
any choice of parameters δi and βi , the objective value of the LP above is at least R0 ≈ 4.086.
However, as stated in Section 2.1, Dlm verifies if after two parts it can migrate its file to
a node A2 being the minimizer of the function
g(x) = [A0 , x] + β10 · [x, R1 ] + β20 · [x, R2 ] ,
where βi0 are parameters that we choose later.
In our analysis, we gave an explicit rule whether the migration to A2 should take place.
However, for our LP-based approach, we follow a slightly different scheme. Namely, if the
migration to A2 guarantees that the amortized cost in the short phase (the first two parts)
is at most 4 times the cost of any strategy for the short phase, then Dlm may move to A2
and we immediately achieve competitive ratio 4 on the short phase. Otherwise, we may
add additional constraints to the LP, stating that the competitive ratio of an algorithm
which moves to A2 is at least 4 (against any chosen strategy OptS). Analogously to OptL,
the trajectory of OptS is described by three points: O0S , O1S , and O2S . This allows us to
strengthen our LP by adding the following inequalities:
P
CALGS = [A0 , A2 ] + i=1,2 δi · [A0 , Ri ] + φ · ([A2 , O2S ] − [A0 , O0S ])
P
req
move
COPTS = i=1,2 (COPTS
(i) + COPTS
(i))
move
S
COPTS
(i) ≥ [Oi−1
, OiS ]

2·

req
COPTS
(i)

+δ·

move
COPTS
(i)

g(A2 ) ≤ g(v)

for i = 1, 2
≥ δi ·

S
[Oi−1
, Ri ]

+ δi ·

[OiS , Ri ]

for i = 1, 2
for all v ∈ V

CALGS ≥ 4 · COPTS
We also change V to {A0 , A3 , O0L , O1L , O2L , O3L , O0S , O1S , O2S }, both in new and in old inequalities.
When we choose φ = 3, fix phase length parameters to be δ1 = 1, δ2 = 0.75, δ3 = 0.5 and
parameters for functions g and h to be β10 = 2, β20 = 1, β1 = 1, β2 = 0.25 and β3 = 0.75, we
obtain that the value of the above LP is 4. Again, this can be interpreted as a numerical
argument that Dlm is indeed a 4-competitive algorithm.

5

Conclusions

While in the last decade factor-revealing LPs became a standard tool for analysis of approximation algorithms, their application to online algorithms so far have been limited to online
bipartite matching and its variants (see, e.g., [24, 20]) and for showing lower bounds [5]. In
this paper, we successfully used the factor-revealing LP to bound the competitive ratio of
an algorithm for an online problem defined on an arbitrary metric space. We believe that
similar approaches could yield improvements also for other online graph problems.
References
1
2
3

Susanne Albers and Hisashi Koga. Page migration with limited local memory capacity. In
Proc. 4th Int. Workshop on Algorithms and Data Structures (WADS), pages 147–158, 1995.
Baruch Awerbuch, Yair Bartal, and Amos Fiat. Competitive distributed file allocation. In
Proc. 25th ACM Symp. on Theory of Computing (STOC), pages 164–173, 1993.
Baruch Awerbuch, Yair Bartal, and Amos Fiat. Heat & Dump: Competitive distributed
paging. In Proc. 34th IEEE Symp. on Foundations of Computer Science (FOCS), pages
22–31, 1993.

M. Bienkowski, J. Byrka and M. Mucha

4
5
6
7
8

9
10
11
12

13

14
15
16
17
18

19

20

21
22
23
24

Baruch Awerbuch, Yair Bartal, and Amos Fiat. Distributed paging for general networks.
Journal of Algorithms, 28(1):67–104, 1998.
Yossi Azar, Ilan Reuven Cohen, and Alan Roytman. Online lower bounds via duality. In
Proc. 28th ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 1038–1050, 2017.
Yair Bartal. Competitive Analysis of Distributed On-line Problems — Distributed Paging.
PhD thesis, Tel-Aviv University, 1995.
Yair Bartal. Distributed paging. In Dagstul Workshop on On-line Algorithms, pages 97–117,
1996.
Yair Bartal, Moses Charikar, and Piotr Indyk. On page migration and other relaxed task
systems. Theoretical Computer Science, 268(1):43–66, 2001. Also appeared in Proc. of the
8th SODA, pages 43–52, 1997.
Yair Bartal, Amos Fiat, and Yuval Rabani. Competitive algorithms for distributed data
management. Journal of Computer and System Sciences, 51(3):341–358, 1995.
Shai Ben-David, Allan Borodin, Richard M. Karp, Gabor Tardos, and Avi Wigderson. On
the power of randomization in online algorithms. Algorithmica, 11(1):2–14, 1994.
Marcin Bienkowski. Migrating and replicating data in networks. Computer Science —
Research and Development, 27(3):169–179, 2012.
Marcin Bienkowski, Jaroslaw Byrka, Miroslaw Korzeniowski, and Friedhelm Meyer auf der
Heide. Optimal algorithms for page migration in dynamic networks. Journal of Discrete
Algorithms, 7(4):545–569, 2009.
David L. Black and Daniel D. Sleator. Competitive algorithms for replication and migration
problems. Technical Report CMU-CS-89-201, Department of Computer Science, CarnegieMellon University, 1989.
Allan Borodin and Ran El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998.
Marek Chrobak, Lawrence L. Larmore, Nick Reingold, and Jeffery Westbrook. Page migration algorithms using work functions. Journal of Algorithms, 24(1):124–157, 1997.
Bezalel Gavish and Olivia R. Liu Sheng. Dynamic file migration in distributed computer
systems. Communications of the ACM, 33(2):177–189, 1990.
Makoto Imase and Bernard M. Waxman. Dynamic Steiner tree problem. SIAM Journal
on Discrete Mathematics, 4(3):369–384, 1991.
Carsten Lund, Nick Reingold, Jeffery Westbrook, and Dicky C. K. Yan. Competitive on-line
algorithms for distributed data management. SIAM Journal on Computing, 28(3):1086–
1111, 1999.
Bruce M. Maggs, Friedhelm Meyer auf der Heide, Berthold Vöcking, and Matthias Westermann. Exploiting locality for data management in systems of limited bandwidth. In Proc.
38th IEEE Symp. on Foundations of Computer Science (FOCS), pages 284–293, 1997.
Mohammad Mahdian and Qiqi Yan. Online bipartite matching with random arrivals: an
approach based on strongly factor-revealing LPs. In Proc. 43rd ACM Symp. on Theory of
Computing (STOC), pages 597–606, 2011.
Akira Matsubayashi. Uniform page migration on general networks. International Journal
of Pure and Applied Mathematics, 42(2):161–168, 2008.
Akira Matsubayashi. A 3+Omega(1) lower bound for page migration. In Proc. 3rd Int.
Symp. on Computing and Networking (CANDAR), pages 314–320, 2015.
Akira Matsubayashi. Asymptotically optimal online page migration on three points. Algorithmica, 71(4):1035–1064, 2015.
Aranyak Mehta, Amin Saberi, Umesh V. Vazirani, and Vijay V. Vazirani. Adwords and
generalized online matching. Journal of the ACM, 54(5), 2007.

A:13

A:14

Dynamic beats fixed: On phase-based algorithms for file migration

25

26

Friedhelm Meyer auf der Heide, Berthold Vöcking, and Matthias Westermann. Provably
good and practical strategies for non-uniform data management in networks. In Proc. 7th
European Symp. on Algorithms (ESA), pages 89–100, 1999.
Jeffery Westbrook. Randomized algorithms for the multiprocessor page migration. SIAM
Journal on Computing, 23:951–965, 1994.

A

Omitted Proofs

I Lemma 3. Let R be set subsequence of at most 2D consecutive requests from the input
issued at steps t + 1, t + 2, . . . , t + |R|. Then, 4 · COPT (R) ≥ (2|R|/D) · [opt , R, opt+|R| ] +
(4 − 2|R|/D) · [opt , opt+|R| ].
Proof. For simplicity of notation, we assume that t = 0. In these terms, R corresponds to
requests r1 , r2 , . . . , r|R| issued at the consecutive steps. By the triangle inequality, for any
y ∈ {0, . . . , R}, it holds that
|R|
|R|
|R|
X
X
X
|R|
· [opy , R] =
d(opy , ri ) ≤
d(opy , opi−1 ) +
d(opi−1 , ri ) .
D
i=1
i=1
i=1

Hence,
|R| 
|R|

X
X
|R|
· [op0 , R, op|R| ] ≤
d(op0 , opi−1 ) + d(op|R| , opi−1 ) + 2
d(opi−1 , ri )
D
i=1
i=1

≤

|R| |R|
X
X

d(opj−1 , opj ) + 2

|R|
X

i=1 j=1

i=1

|R|
X

|R|
X

= |R|

d(opj−1 , opj ) + 2

d(opi−1 , ri )

d(opi−1 , ri ) .

i=1

j=1

Finally,


2|R|
2|R|
· [op0 , R, op|R| ] + 4 −
· [op0 , op|R| ]
D
D


|R|
X
2|R|
·D·
d(opi−1 , opi )
≤4
d(opi−1 , ri ) + 2|R|
d(opi−1 , opi ) + 4 −
D
i=1
i=1
i=1
|R|
X

=4

|R|
X

|R|
X

d(opi−1 , ri ) + 4D

i=1

|R|
X

d(opi−1 , opi )

i=1

= 4 · COPT (R) .

B

J

Lower Bound for Phase-Based Algorithms

In this section, we show that, under some additional assumptions, no fixed-phase algorithm
can beat the competitive ratio R0 ≈ 4.086 achieved by Mtlm (see Section 1.2), where R0 is
the largest (real) root of the equation
R3 − 5R2 + 3R + 3 = 0 .

(11)

Let vopt and valg be the positions of files of Opt and Alg, respectively. Alg and Opt
start at the same point of the metric. Recall that a fixed-phase algorithm chooses phase

M. Bienkowski, J. Byrka and M. Mucha

length c · D and after every c · D requests it makes a migration decision solely on the basis
of its current position and the last c · D requests. In particular, it cannot store the history
of past requests beyond the window consisting of the last c · D requests. Bartal et al. [8]
showed that no fixed-phase algorithm can achieve competitive ratio better than 3.847 (for D
tending to infinity).
We present our lower bound in a model that gives an additional power to the adversary.
Let f denote the distance between valg and vopt at the end of a phase. Then, at the beginning
of the next phase P , the adversary removes the existing graph and creates a completely new
one in which it chooses a new position for valg . It creates a sequence of requests constituting
phase P and runs Alg on P . Finally, it chooses a strategy for Opt for P , with the restriction
that the initial distance between Opt and Alg files is exactly f . We call this setting dynamic
graph model.

B.1

Using known lower bound for short phases

The lower bound given for fixed-phases algorithms by Bartal et al. [8] is already sufficient to
show the desired lower bound for shorter phase lengths. (It can also be used for very long
phases, but we do not use this property.)
I Lemma 4. Let cT = 2(R0 + 1)/(R02 − 2R0 − 1) ≈ 1.352. No fixed-phase algorithm using
phase lengths c · D with c ≤ cT can achieve competitive ratio lower than R0 .
Proof. Theorem 3.2 of [8] states that no algorithm using phases of length c · D can have
competitive ratio smaller than


c+2
a
,
+ 1, c · (a + 1) + 1 .
(12)
L(c) = inf max
1 − a ca
a∈(0,1)
Theorem 3.2 of [8] also shows that L(c) ≥ 3.847 for any c. However, we may also analyze
this bound restricting phase lengths. In particular, we claim that when c ≤ cT := 2(R0 +
1)/(R02 − 2R0 − 1), then L(c) ≥ R0 . To see this, consider two cases. When a > R0 /(1 + R0 ),
the first term of (12), a/(1 − a), is already greater than R0 . Otherwise, a < R0 /(1 + R0 )
and for c ≤ cT , the second term of (12), (c + 2)/(ca) + 1, is at least R0 .
J

B.2

States

As mentioned in the informal introduction given in Section 3, our adversarial construction will
consists of multiple epochs, each consisting of multiple phases. In each phase, the adversary
will employ one of three possible plays: linear, bipartite or finishing, which were sketched in
Section 3 and will be formally introduced in the subsequent sections.
Our construction will be parameterized with integers L and k; the latter is a parameter
used in the bipartite play. We define
(∞
)


X
4R
(2α)L 4R0
0
i
ε = max
(2α) ,
= max
,
,
k+4
1 − 2α k + 4
i=L

where α = 1/(R0 − 1). Note that ε tends to zero with increasing L and k. Our goal is to
show that for any epoch E it holds that CALG (E) ≥ (R0 − ε) · COPT (E). As ε can be made
arbitrarily small, this will imply the lower bound of R0 .
The relation CALG (M ) ≥ (R0 − ε) · COPT (M ) does not hold for each adversarial play M .
Nonetheless, we want to measure the amount CALG (M ) − (R0 − ε) · COPT (M ) for each

A:15

A:16

Dynamic beats fixed: On phase-based algorithms for file migration

play M ; we call this amount play gain. For a single play M , different behaviors of Alg can
result in different play gains and final values of d(valg , vopt ).
First, we define possible states. A state is defined between phases and depends on the
distance between valg and vopt .
1. State S: valg = vopt .
2. State A` for ` ∈ {0, . . . , L}: d(valg , vopt ) = (2α)` , where α = 1/(R0 − 1).
3. State F : all remaining distances between valg and vopt .
In the following sections, we define adversarial plays: for each state there will be one play
that can start at this state. For each play, we will then characterize possible outcomes: play
gains and the resulting states. Finally, we analyze the total gain on any sequence of plays
and we show that it can be lower-bounded by a constant. This will imply Theorem 2.

B.3

Starting in state S: linear play

I Lemma 5. Assume a phase starts in state S. Then, the adversary may employ a singlePL−1
phase (linear) play, whose gain is at least − i=0 (2α)i · D and which always ends in
state A0 .
Proof. At the beginning of a linear play, valg = vopt . The created graph consists of two
nodes, a = valg = vopt and b, connected with an edge of length 1. Let t = 1 + 1/R0 ≈ 1.245.
Observe that t < c for all considered lengths c · D of a phase. The play consists of a single
phase P , whose first (c − t) · D requests are given at a and the following t · D requests are
given at b.
Note that Alg pays 1 for each of the last t requests. We consider two cases depending
on the possible action of Alg at the end of P .
1. Alg migrates the file to b. In this case CALG (P ) = (t + 1) · D. Opt then chooses to keep
its file at a throughout P paying t · D. Then,
CALG (P ) − R0 · COPT (P ) = (t + 1 − R0 · t) · D = (1/R0 + 1 − R0 ) · D .
2. Alg keeps the file at a. In this case CALG (P ) = t · D. Opt then remains at a for the
first c − t requests, migrates its file to b, and keeps it there till the end of P . Altogether,
COPT (P ) = D. Then,
CALG (P ) − R0 · COPT (P ) = (t − R0 · 1) · D = (1/R0 + 1 − R0 ) · D .
In both cases, the resulting state is A0 . Using the definition of R0 (see (11)), it can be
verified that R0 − 1 − 1/R0 = (R0 − 1)/(R0 − 3). By the definition of α, this is equal to
1/(1 − 2α). Therefore, using COPT (P ) ≥ D, we obtain that the play gain is
CALG (P ) − (R0 − ε) · COPT (P ) = ε · COPT (P ) − (R0 − 1 − 1/R0 ) · D
!


∞
X
1
i
≥ ε−
·D = ε−
(2α) · D
1 − 2α
i=0
≥ −

L−1
X
i=0

(2α)i · D .

J

M. Bienkowski, J. Byrka and M. Mucha
Q

A:17
S

a

a
f

b

α·f

Figure 2 An example of graph used in the bipartite play for k = 3 (left) and a graph used in
the linear play (right). Note that they correspond to tight examples for the performance of the
algorithm Mtlm.

B.4

Starting in state A` : bipartite play

I Lemma 6. Assume a phase starts in state A` for ` ∈ {0, . . . , L − 1}. Then, the adversary
may employ a single-phase (bipartite) play, such that one of the following conditions hold:
1. the resulting state is A` and the play gain is at least zero;
2. the resulting state is A`+1 and the play gain is at least (2α)` · D;
3. the resulting state is F with valg -vopt distance equal to 3α · (2α)` and the play gain is at
least (1 + α) · (2α)` · D.
Proof. Let f = (2α)` denote the initial value of d(valg , vopt ). Let a denote the initial position
of Alg’s file.
Phase construction. The construction of this play will be parameterized by an integer
k ≥ 3. The graph created by the adversary will be bipartite and consists of the following
three parts: {a}, set Q, and set S, where |Q| = |S| = k, see Figure 2. As allowed in the
dynamic graph model, the exact initial position of vopt will be determined later based on the
behavior of Alg; in any case it will be initially in set Q. Node a is connected with all nodes
from Q with an edge of length f . The connections between Q and S constitute an almost
complete bipartite graph, whose edges are of length α · f . Namely, we number all nodes from
Q and S as q1 , q2 , . . . , qk and s1 , s2 , . . . , sk , respectively, and we connect qi with sj if and
only if i 6= j. An example for k = 3 is given in Figure 2. As k ≥ 3, any pair of nodes from S
share a common neighbor from Q and hence the distance between them is exactly 2α · f .
All the requests are given at nodes from S in a round-robin fashion (the adversary fixes
an arbitrary ordering of nodes from S first). As D is sufficiently large, each node of S issues
at least one request.
Cost analysis. In either case Opt remains at one node from Q for the whole phase P . It
pays α · f for any request at k − 1 neighboring nodes from Q and 3α · f for any request at the
only non-incident node from Q. As requests are given in a round-robin fashion, the number
of requests at that non-incident node is m ≤ dcD/ke ≤ 2cD/k, and the total cost of Opt is
COPT (P ) = α · f · (cD − m) + 3α · f · m
= α · f · (cD + 2m)
≤ (1 + 4/k) · α · f · cD .
By the definition of ε, it holds that (R0 − ε) · (1 + 4/k) = R0 + (4R0 /k − ε · (1 + 4/k)) ≤ R0 .
R
Furthermore, we split the cost of Alg on P into the cost of serving the requests, CALG
(P ),

A:18

Dynamic beats fixed: On phase-based algorithms for file migration

M
R
and the migration cost CALG
(P ). The former is exactly CALG
(P ) = (1+α)·f ·cD. Therefore,
M
R
CALG (P ) − (R0 − ε) · COPT (P ) = CALG
(P ) + CALG
(P ) − (R0 − ε) · COPT (P )
M
≥ CALG
(P ) + (1 + α) · f · cD − R0 · α · f · cD
M
= CALG
(P ) ,

where the last equality follows as R0 · α = 1 + α by the definition of α. Hence, for lowerM
bounding the play gain, it is sufficient to lower-bound CALG
(P ). We consider several possible
migration options for Alg on the bipartite play.
M
1. Alg remains at a. In this case CALG
(P ) = 0, and the resulting state is still A` .
2. Alg migrates the file to a node q ∈ Q, paying f · D = (2α)` · D for the migration. The
adversary chooses its original position to be any node from Q different from q. Therefore,
the final distance between Alg and Opt files is exactly 2α · f . The resulting state is
M
A`+1 and the play gain is at least CALG
(P ) = (2α)` · D.
3. Alg migrates the file to a node s ∈ S. The adversary chooses its original position to be
(the only) node from Q not directly connected to s. The cost of migration is (1 + α) · f · D
and the resulting distance between Alg and Opt files is then 3α · f , i.e., the play ends
in state F .
J

B.5

Starting in states F and AL : finishing play

I Lemma 7. Assume a phase starts in state AL or F and the initial distance between valg
and vopt is f . Then, the adversary may employ a (finishing) play, whose gain is at least
(c + 1) · f · D and which always ends in state S.
Proof. In this case the adversary uses a finishing play M . This is the only play that may
consist of more than one phase. It is played on two nodes valg and vopt , connected by an edge
of length f . In a phase of this play, Opt never moves and all requests are issued at vopt .
If at the end of the phase Alg does not migrate the file to vopt , the adversary repeats the
phase.
The cost of Opt in any such phase is 0. Hence, any competitive algorithm has to finally
migrate to vopt , possibly over a sequence of multiple phases, i.e., the final state is always of
type S. In the first phase of M , Alg pays at least c · D · f for the requests. Furthermore,
within M , Alg migrates the file along the distance of at least f , paying f · D. The play gain
is then
CALG (M ) − (R0 − ε) · COPT (M ) ≥ CALG (M ) ≥ (c + 1) · f · D .

B.6

J

Combining all plays

In Figure 3, we summarized the possible transitions between states, as described in Lemma 5,
Lemma 6, and Lemma 7. We may now use this state graph to show the desired lower bound.
I Lemma 8. Fix any algorithm Alg and a input (sub)sequence I consisting of some number
of plays, such that Alg starts and ends I at state S. Then, the total gain on all plays from I
is non-negative.
Proof. For a transition between two states Q1 and Q2 , we denote its gain by T (Q1 , Q2 ). By
Lemma 6, T (A` , A` ) ≥ 0 for any ` ∈ {0, . . . , L − 1}. Thus, we may ignore loops at A` when
computing total plays’ gain. There are two possibilities:

M. Bienkowski, J. Byrka and M. Mucha

A:19

F

S

−

PL−1
i=0

(2α)i · D

A0

(2α)0 · D

≥0

A1

(2α)1 · D

AL−1

A2

≥0

≥0

(2α)L−1 · D

AL

≥0

≥0

Figure 3 Plays as transitions between states. Note that state F corresponds to many possible
configurations with different distances between valg and vopt . The gains for all plays that avoid
state F are given at the corresponding edges.

1. The game starts at state S, goes through states A0 , A1 , . . . , AL−1 , AL (possibly looping
at some A` ’s), and returns to S. The total plays’ gain is then
L−1
X

T (S, A0 ) +

T (A` , A`+1 ) + T (AL , S) ≥ −

L−1
X

i

(2α) · D +

i=0

`=0

L−1
X

(2α)` · D ≥ 0 .

`=0

2. The game starts at state S, goes through states A0 , A1 , . . . , Am (for m < L, possibly
looping at some A` ’s), then to state F , and returns to S. Note that the distance between
valg and vopt at state Am is (2α)m and therefore this distance in state F is 3α · (2α)m .
The total plays’ gain is then
T (S,A0 ) +

m−1
X

T (A` , A`+1 ) + T (Am , F ) + T (F, S)

`=0

≥ −

L−1
X

(2α)i · D +

i=0

m−1
X

(2α)` · D + (1 + α)(2α)m · D + (c + 1) · 3α · (2α)m · D

`=0

= (2α)m · D ·

(1 + α) + (c + 1) · 3α −

L−m−1
X

!
(2α)i

i=0
m



≥ (2α) · D · (1 + α) + (c + 1) · 3α −

1
1 − 2α



≥0 .
The last inequality can be verified numerically: for α = 1/(R0 − 1) ≈ 0.324 and c ≥ cT =
2(R0 + 1)/(R2 − 2R0 − 1) ≈ 1.352, it holds that (1 + α) + (c + 1) · 3α − 1/(1 − 2α) >
0.768 > 0.
J
I Theorem 2. Fix any algorithm Alg that operates in phases of fixed length. Assume
that between the phases, the adversary can arbitrarily modify the graph while keeping the
distance between the files of Opt and Alg unchanged. Then, the competitive ratio of Alg
is at least R0 (for D tending to infinity), where R0 ≈ 4.086 is the competitive ratio of
algorithm Mtlm.
Proof. We consider a sequence of state transitions that starts from state S. Assume that we
run Alg infinitely and we observe its behavior.
If on an infinite sequence, Alg always returns to state S, then for an actual input we
take any prefix I of this infinite sequence ending at state S. By Lemma 8, CALG (I) ≥
(R0 − ε) · COPT (I) and CALG (I) can be made arbitrarily large by taking sufficiently long I.
As ε can be made arbitrarily small, the theorem follows.

A:20

Dynamic beats fixed: On phase-based algorithms for file migration

Otherwise, Alg run on this infinite sequence returns to S fixed number of times, then
reaches state A` (for ` ∈ {0, . . . , L − 1}), and then loops infinitely at A` . If we stop the
infinite sequence after some some number of such loops, it defines an actual finite sequence I,
0
0
1
1
2
2
`
`
consisting of 1 + 2(` + 1) parts: Iinit , Itrans
, Iloop
, Itrans
, Iloop
, Itrans
, Iloop
, . . . , Itrans
, Iloop
,
where
1. Iinit starts and ends at S;
i
2. Itrans
starts at Ai−1 and ends at Ai (where by A−1 we understand S);
i
3. Iloop
loops at Ai .
i
Some parts Iloop
may be non-existing (empty sub-sequences). As in the previous case,
the total plays’ gain on Iinit is non-negative. By Lemma 6, the same holds also for any
i
part Iloop
. Therefore,

CALG (I) = CALG (Iinit ) +

P`

i=0
P`
i=0

i
i
CALG (Itrans
) + CALG (Iloop
)



i
≥ CALG (Iinit ) +
CALG (Iloop
)


P`
i
≥ (R0 − ε) · COPT (Iinit ) + i=0 COPT (Iloop
)


P`
i
= (R0 − ε) · COPT (I) − i=0 COPT (Itrans
) .
i
On the other hand, the total cost of Opt on all parts Itrans
can be upper-bounded by
a universal constant γ, independent of I. Thus, CALG (I) ≥ (R0 − ε) · COPT (I) − (R0 − ε) · γ.
As CALG (I) can be made arbitrarily large (the cost of any loop from A` to A` is universally
lower-bounded), the term (R0 − ε) · γ becomes negligible on the long run. Again, as ε can be
made arbitrarily small, the theorem follows.
J

