Competitive On-Line Algorithms for Distributed Data Management.
Competitive on-line algorithms for data management in a network of processors are studied in this paper. A data object such as a file or a page of virtual memory is to be read and updated by various processors in the network. The goal is to minimize the communication costs incurred in serving a sequence of such requests. Distributed data management on important classes of networks---trees and bus-based networks---are studied. Optimal algorithms with constant competitive ratios and matching lower bounds are obtained. Our algorithms use different interesting techniques, such as work functions [Chrobak and Larmore, Proc. DIMACS Workshop on On-Line Algorithms, AMS, 1991, pp. 11--64] and "factoring."
Introduction
. The management of data in a distributed network is an important
and much studied problem in management science, engineering, computer
systems and theory [3, 11]. Dowdy and Foster [11] give a comprehensive survey of
research in this area, listing eighteen different models and many papers. A data ob-
ject, F, such as a file, or a page of virtual memory, is to be read and updated by a
network of processors. Each processor may store a copy of F in its local memory,
so as to reduce the time required to read the data object. All copies must be kept
consistent, however; so having multiple copies increases the time required to write to
the object. As read and write requests occur at the processors, an on-line algorithm
has to decide whether to replicate, move, or discard copies of F after serving each
request, while trying to minimize the total cost incurred in processing the requests.
The on-line algorithm has no knowledge of future requests, and no assumptions are
made about the pattern of requests. We apply competitive analysis [6] to such an
algorithm.
Let oe denote a sequence of read and write requests. A deterministic on-line
algorithm A is said to be c-competitive, if, for all oe, CA (oe)  c \Delta OPT
where CA (oe) and OPT (oe) are the costs incurred by A and the optimal off-line solution
respectively, and c and B are functions which are independent of oe, but which may
depend upon the input network and file size. If A is a randomized algorithm, we
replace CA (oe) by its expected cost and consider two types of adversaries: the oblivious
adversary chooses oe in advance, and the more powerful adaptive on-line adversary
builds oe on-line, choosing each request with knowledge of the random moves made
by A on the previous requests. The oblivious adversary is charged the optimal off-line
cost, while the adaptive on-line adversary has to serve oe and be charged on-line.
(See Ben-David et al. [6] for a full discussion of different types of adversaries.) An
algorithm is strongly competitive if it achieves the best possible competitive ratio.
In this paper, we focus on two important classes of networks: trees and the
uniform network. A tree is a connected acyclic graph on n nodes and (n \Gamma 1) edges;
A preliminary version of this paper has appeared in [19].
y Research, AT&T Labs, 600-700 Mountain Avenue, Murray Hill, NJ 07974-0636, U.S.A. e-mail:
lund@research.att.com, reingold@research.att.edu, and westbrook@research.att.com
z This work was performed while the author was at Yale University. Research partially supported
by NSF Grant CCR-9009753.
x Department of Operations Research, AT&T Labs, Room 3J-314, 101 Crawfords Corner Road,
Holmdel, NJ 07733-3030, U.S.A. This work was performed while the author was at Yale University.
Research partially supported by Fellowships from Yale University. e-mail:yan@att.com
J. WESTBROOK, and D. YAN
the uniform network is a complete graph on n nodes with unit edge weights. We
obtain strongly competitive deterministic and randomized on-line algorithms for these
classes.
Our algorithms use different interesting techniques such as offset functions and
"factoring." Competitive on-line algorithms based on offset functions have been found
for the 3-server [9] and the migration problems [10]. An advantage of these algorithms
is they do not need to record the entire history of requests and the on-line algorithm,
since decisions are based on the current offset values which can be updated easily.
Factoring is first observed in [7] and used in [10, 17]. The idea is to break down
an on-line problem on a tree into single edge problems. Thus strongly competitive
strategies for a single edge is generalized to a tree. Our algorithms are strongly
competitive for specific applications and networks, and also illustrate these two useful
techniques. Our randomized algorithm for file allocation is barely random [20], i.e.,
it uses a bounded number of random bits, independent of the number of requests. A
random choice is made only at the initialization of the algorithm, after which it runs
deterministically.
1.1. Problem Description. We study three variants of distributed data man-
agement: replication [1, 7, 17], migration [7, 10, 22] and file allocation
They can be can be described under the same framework. We are given an undirected
graph E) with non-negative edge weights and jV represents
a processor. Let F represent a data file or a page of memory to be stored in
the processors. At any time, let R ' V , the residence set, represent the set of nodes
that contain a copy of F. We always require R 6= ;. Initially, only a single node v
contains a copy of F and
A sequence of read and write requests occur at the processors. A read at processor
requests an examination of the contents of some data location in F ; a write at
processor p requests a change to the contents of some location in F. The location
identifies a single word or record in F . A read can be satisfied by sending a message
to any processor holding a copy of F ; that processor then returns the information
stored in the requested location. A write is satisfied by sending an update message to
each processor holding a copy F , telling it how to modify the desired location. After
a request is served, the on-line server can decide how to reallocate the multiple copies
of F.
be an integer constant, D  1, which represents the number of
records in F. 1 The costs for serving the requests and redistributing the files are as
follows.
Service Cost: Suppose a request occurs at a node v. If it is a read
request, it is served at a cost equal to the shortest path distance from
v to a nearest node in R; if it is a write request, it is served at a cost
equal to the size of the minimum Steiner tree 2 that contains all the
nodes in R [ fvg.
Movement Cost: The algorithm can replicate a copy of F to a node
v at a cost D times the shortest path distance between v and the
nearest node with a copy of F ; it can discard a copy of F at no cost.
A file reallocation consists of a sequence of zero or more replications and discards of
+represent the sets of reals, positive integers and non-negative integers,
respectively.
section 2 for a definition.
ON-LINE DISTRIBUTED
copies of F . The replications and allocations can be done in any order as long as the
residence set has size at least 1. The movement cost incurred during a reallocation is
equal to the total sum of all replication costs.
The replication and migration problems are special cases of file allocation. For
migration, we require 1. For replication, all the requests are reads, and it can be
assumed that all replicated copies of F are not discarded. The (off-line) optimization
problem is to specify R after each new request is served so that the total cost incurred
is minimized. For on-line replication, we only consider competitive algorithms that
have in the inequality above; otherwise a trivial 0-competitive algorithm exists
Following previous papers on allocation and related problems, we adopt a
"lookahead-0" model. In this model, once a request is revealed, the on-line algorithm
must immediately pay the service cost before making any changes to the residence
set. One may contrast lookahead-0 with a lookahead-1 model, in which the algorithm
may change the residence set before paying the service cost. We discuss the lookahead
issue further below, together with some implementation issues.
1.2. Previous and Related Results. Black and Sleator [7] were the first to
use competitive analysis to study any of these problems, giving strongly 3-competitive
deterministic algorithms for file migration on trees and uniform networks, and strongly
2-competitive deterministic algorithms for replication on trees and uniform networks.
Replication: Imase and Waxman [14] showed that a greedy algorithm for building
Steiner trees on-line is \Theta(log n)-competitive, where n is the number of nodes, and
that this ratio is optimal within constant factors for general networks. This algorithm
is the basis of a solution for on-line replication in general networks. Koga [17] gave
randomized algorithms that are 2-competitive and 4-competitive against an adaptive
on-line adversary on trees and circles, respectively. He also obtained a randomized
algorithm with a competitive ratio that depends only on D and approaches (1+1=
as D grows large, against an oblivious adversary on trees.
Migration: Westbrook [22] obtained a randomized algorithm for uniform networks
with a competitive ratio that depends only on D and approaches ((5
as
D grows large, against an oblivious adversary, For general networks, Westbrook [22]
obtained a strongly 3-competitive randomized algorithm against an adaptive on-line
adversary. He also obtained an algorithm against an oblivious adversary with a competitive
ratio that depends only on D and approaches (1 OE)-competitive as D grows
large, where OE  1:62 is the golden ratio. Chrobak et al. [10] studied migration on various
classes of metric spaces including trees, hypercubes, meshes, real vector spaces,
and general products of trees. They gave strongly (2+1=2D)-competitive randomized
algorithms for these spaces, (2+1=2D)-competitive deterministic algorithms for some
of these spaces, and a general lower bound for deterministic algorithms of (85=27).
Recently, Bartal et al. [4] obtained a 4:086-competitive deterministic algorithm.
File Allocation: For general networks, Awerbuch et al. [2] and Bartal et al. [5] give
O(logn)-competitive deterministic and randomized algorithms against an adaptive
on-line adversary, respectively. Westbrook and Yan [23] show that Bartal et al.'s
algorithm is O(logd(G))-competitive on an unweighted graph with diameter d(G),
and there exists a O(log 2 d(G))-competitive deterministic algorithm. Bartal et al.
also find a (3 +O(1=D))-competitive deterministic algorithm on a tree, and strongly
3-competitive randomized algorithms against an adaptive on-line adversary on a tree
and uniform network. Since replication is a special case of file allocation, these upper
bounds are also valid for replication when the additive constant B is zero.
4 C. LUND, N. REINGOLD, J. WESTBROOK, and D. YAN
Replication Migration File Allocation
Randomized uniform e D =(e
tree e D =(e
this paper

Table
The State of the Art: Trees and Uniform Networks. Note e
1.3. New Results. This paper contributes the following results.
ffl For on-line file allocation on a tree, we give a strongly 3-competitive deterministic
algorithm and a (2+1=D)-competitive randomized algorithm against
an oblivious adversary, and show that this is optimal even if G is an edge.
ffl For uniform networks, we show that the off-line file allocation problem can
be solved in polynomial time. We give a strongly 1=(2D))-competitive
randomized on-line algorithm for migration against an oblivious adversary on
the uniform network.
ffl For the replication problem, we show that the off-line problem is NP-hard; this
implies the file allocation problem is also NP-hard. We obtain randomized
algorithms that are (e D =(e D \Gamma 1))-competitive against an oblivious adversary
on a tree and a uniform network; this is optimal even if G is a an edge.
(Albers and Koga [1] have independently obtained the same results for on-line
replication using a different method.)
ffl We show that no randomized algorithm for replication on a single edge can
be better than 2-competitive against an adaptive on-line adversary. Thus
Koga's [17] algorithm for replication on a tree is strongly competitive.

Table

1 summarizes the competitive ratios of the best known deterministic and
randomized algorithms against an oblivious adversary for replication, migration, and
file allocation on trees and uniform networks. They are all optimal.
1.4. Lookahead and Implementation Issues. As stated above, we adopt
the lookahead-0 model that has been used in all previous work on allocation and its
variants. Studies of some other on-line problems, however, have used a lookahead-1
model, and in this subsection we comment briefly on the distinction.
In a lookahead-1 model of allocation, some request sequences could be served
by an on-line algorithm at a lower cost than would be possible in the lookahead-0
model. For example, if a write request occurs, a lookahead-1 algorithm can drop all
but one copies of F before servicing the request, thereby reducing the service cost.
The lookahead-0 model is more appropriate for file allocation, however, because the
service cost models both the message cost of satisfying a request, which includes the
cost of transmitting an answer back to a read request or passing an update on to
all copies, and the message cost of the control messages that must be transmitted in
order for the algorithm to learn of new requests and to implement its replication and
drop decisions. Specifically, we assume that a new replication will not occur unless at
least one member of the replication set has been told of a new request, and a processor
will not discard a copy unless it has been told of a new write request.
We claim that for large values of D the optimal competitive ratio in a lookahead-1
model is not materially different than the optimal competitive ratio in a lookahead-0
model. In particular, if there is a c-competitive algorithm using lookahead-1, there
is a 2=D)-competitive algorithm using lookahead-0. The lookahead-0 algorithm
ON-LINE DISTRIBUTED
simulates the lookahead-1 algorithm by keeping the same residence set. When the
lookahead-1 algorithm saves service cost on a read, the amount saved can be no more
than the distance it replicates files just prior to the satisfying the request. Similarly,
when the lookahead-1 algorithm saves service cost on a write, the amount saved can
be no more than the weight of a minimum Steiner tree which connects the dropped
copies to an undropped copy. But at some point in the past, at least one of the
dropped copies must have been replicated over each edge in that Steiner tree. Hence
for each unit of distance saved on reads by the lookahead-1 algorithm, one file was
moved one unit of distance. The same holds for writes. The the total cost saved by
the lookahead-1 algorithm is 2
times the total movement cost. Both algorithms incur
the same movement cost, however.
One may ask whether our service cost is too optimistic: could our algorithms
actually be implemented using only the control messages accounted for in the service
cost. Although we do not directly address this issue, our algorithms are essentially
distributed in nature and can be implemented with only constant message overhead
in the special case of uniform and tree networks.
2. Preliminaries. We use the technique of work functions and offset functions
introduced by Chrobak and Larmore [9]. Let S be a set of states, one for each legal
residence set. Thus S is isomorphic to 2 V n f;g. Let R(s) denote the residence set
corresponding to state s 2 S. We say the file system is in state s if the current
residence set is R(s); s 2 S. Let be the set of possible requests,
requests at node v, respectively. A request
sequence revealed to the on-line algorithm, with each oe i 2 Y .
Suppose the network is in state s when oe i arrives. The algorithm will be charged a
service cost of ser(s; oe i ), where ser(s; oe \Gamma!R is as described in Section 1.1.
After serving oe i , the algorithm can move to a different state t at a cost tran(s;
\Gamma!R is the minimum cost of moving between the two residence
sets.
The work function W i (s) is the minimum cost of serving requests 1 to i, terminating
in state s. Given oe, a minimum cost solution can be found by a dynamic
programming algorithm with the following functional equation:
with suitable initializations. Let opt be the optimal cost of
serving the first i requests. We call the offset function value
at state s after request i has been revealed. Define \Deltaopt it is the
increase in the optimal off-line cost due to oe i .
Our on-line algorithms make decisions based on the current offset values,
S. Note that to compute the ! i (s)'s and \Deltaopt i 's, it suffices to know only the ! i\Gamma1 (s)'s.
to show that an algorithm A is c-competitive, we need
only show that for each reachable combination of offset function, request, and file
system state, the inequality \DeltaC A + \Delta\Phi  c \Delta \Deltaopt i holds, where \DeltaC A is the cost
incurred by A and \Delta\Phi is the change in some defined potential function. If the total
change in \Phi is always bounded or non-negative, summing up the above inequality
over oe, we have CA (oe)  c \Delta OPT (oe) +B where B is some bounded value.
The Steiner Tree Problem:
We shall refer to a network design problem called the Steiner tree problem (STP) [24]
which can be stated as follows. An instance of STP is given by a weighted undirected
6 C. LUND, N. REINGOLD, J. WESTBROOK, and D. YAN
graph E), a weight function on the edges
0 , a subset Z ' V of
regular nodes or terminals, and a constant B . The decision problem is to ask
if there exists a Steiner tree in G that includes all nodes in Z and has a total edge
weight no more than B 0 . STP is NP-complete even when G is restricted to bipartite
graphs with unit edge weights, or to planar graphs [12, 16]. Surveys on STP can be
found in [13, 24]. On a tree network, the union of paths between all pairs of terminals
gives the optimal Steiner tree.
3. Deterministic Algorithms for FAP on a Tree. We begin by introducing
some concepts that will be used in building both deterministic and randomized
algorithms for file allocation on trees.
We say a residence set is connected if it induces a connected subgraph in G. On
a tree, if the residence set is always connected, each node without a copy of F can
easily keep track of R, and hence the nearest copy of F, by using a pointer. In fact,
when G is a tree we can limit our attention to algorithms that maintain a connected
R at all times.
Theorem 3.1. On a tree, there exists an optimal algorithm that always maintains
a connected residence set, i.e., given any (on-line or off-line) algorithm A, there exists
an algorithm A 0 that maintains a connected R and CA 0 (oe)  CA (oe) for all oe. If A is
on-line, so is A 0 .
Proof. Let R(A) and be the residence sets maintained by A and A 0 , re-
spectively. We simulate A on oe and let A 0 be such that at any time, R(A 0 ) is the
minimum connected set that satisfies R(A) ' Given R(A), on a tree,
is defined and unique.
reading cost incurred by A 0 cannot be greater than that
by A. The same holds true for the writing cost issued at any node v, since
spans the unique minimum length Steiner tree for R(A) [ fvg. So A 0 does not incur
a greater read or write cost than A.
Algorithm A 0 does not need to carry out any replication unless A does, and only
to nodes that are not already in should leave
a copy of F along any replication path, this can be done without incurring any extra
cost. As R(A) ' never needs to traverse a replication path longer than
that by A for the same replication. Hence, A 0 cannot incur a greater replication cost.
Since a reallocation is a sequence of replications and discards of F, A 0 maintains a
connected set at all times and does not incur a great cost than A in the reallocation.
Henceforth we shall only consider algorithms that maintain a connected residence
set R at all times. When we say that an algorithm replicates to node v, we shall mean
it leaves a copy of F at all nodes along the shortest path from the residence set to v.
In a tree network we can make some additional simplifying assumptions. Suppose an
algorithm A decides to move to residence set R 0 from set R. This reallocation involves
a some sequence of replications and drops.
Lemma 3.2. All replications can be performed before all drops without increasing
the total cost of the reallocation.
Proof. Dropping a copy can only increase the cost of subsequent replications.
Henceforth we assume that all algorithms comply with Lemma 3.2.
Lemma 3.3. Let R be the nodes that gain a copy of F . Then F can be
replicated to the nodes of S in any order at total cost D \Delta jT (R 0
is the subtree induced by node set R.
Proof. A copy of F must be sent across each edge in T (R 0 (R) at least once.
ON-LINE DISTRIBUTED
But in any order of replication, a copy cannot be sent across an edge more than once,
because then both endpoints contain a copy of F .
Henceforth we assume that all algorithms comply with Lemma 3.3.
A useful tool in handling on-line optimization on trees is factoring [7, 10]. It
makes use of the fact that any sequence of requests oe and any tree algorithm can be
"factored" into (n \Gamma 1) individual algorithms, one for each edge. The total cost in the
tree algorithm is equal to the sum of the costs in each individual edge game. For edge
(a; b) we construct an instance of two-processor file allocation as follows. The removal
of edge (a; b) divides T into two subtrees T a and T b , containing a and b, respectively.
A read or write request from a node in T a is replaced by the same kind of request
from a, and a request from a node in T b is replaced by the same request from b. Let
A be an algorithm with residence set R(A). Algorithm A induces an algorithm on
edge (a; b) as follows: if R(A) falls entirely in T a or T b then the edge algorithm is
in state a or b, respectively; otherwise, the edge algorithm is in state ab. When the
edge algorithm changes state, it does so in the minimum cost way (i.e. at most one
replication). This factoring approach is used in our algorithms for file allocation on a
tree. For the rest of this paper, given an edge (a; b), we use T a and T b to represent
the subtrees described above, s to denote the state the edge is in, and let the offset
functions triplet be is the offset function value
of state s after oe i has arrived.
Lemma 3.4. For algorithm A and request sequence oe, let A (a;b) be the algorithm
induced on edge (a; b), and oe ab be the request sequence induced on edge (a; b). Then
(a;b)2E
(oe ab
Proof. We show that the cost incurred by any event contributes the same amount
to both sides of the equation.
For a write request at a node v, CA (oe) increases by the weight of the unique
Steiner tree, T 0 , containing nodes in R(A) [ fvg. In the induced problem of any edge
e on T 0 , the residence set and the request node are on opposite sides of e, and a write
cost equal to e's weight is incurred. For other edges, v and the residence set lie on
the same side of e, and no cost is incurred in their induced problems. So both sides
of the equation increase by the same amount.
For a read request at a node v, the same argument as in the write case can be
used, replacing T 0 by the unique path from v to the nearest node with a copy of F.
Both sides of the equation increase by the same amount.
Suppose A moves from a residence set of R to R 0 , and consider the sequence of
replications and discards that make up the reallocation process. We show by induction
on the length of this sequence that the movement cost to A is exactly equal to the sum
of movement costs in the induced edge problems. Suppose that the first action in the
sequence is to replicate F to node v. The cost to A is D times the sum of the lengths
of the edges on the shortest path from R to v. Since R is connected, the edges on this
path are exactly the edges that must replicate in their induced problems. Thus both
sides of the equation increase by the same amount. If the first action is a discard,
then no costs are incurred by A or any of the induced edge algorithms.
Lemma 3.5. Let OPT (oe ab ) be the cost incurred by an optimal edge algorithm for
(a; b) on sequence oe ab . Then
(a;b)2E OPT (oe ab )  OPT (oe).
Proof. The Lemma follows by letting A in Lemma 3.4 be the optimal off-line
algorithm for FAP on a tree, and noting CA (a;b)
(oe ab )  OPT (oe ab ) for any A and edge
8 C. LUND, N. REINGOLD, J. WESTBROOK, and D. YAN
(a; b).
It follows from Lemmas 3.4 and 3.5 that if A is an on-line algorithm such that on any
oe, and for each edge (a; b), CA (a;b)
(oe ab )  c \Delta OPT (oe ab ) holds, then A is c-competitive.
To construct a deterministic algorithm for the tree, we first construct a suitable
optimal algorithm for a single edge We then design the tree algorithm so that it induces
this optimal edge algorithm in each edge, thereby guaranteeing competitiveness.
3.1. An Optimal Deterministic Edge Algorithm. Let be an
edge, and abg the set of states the file system can be in-only node a
has a copy, only node b has a copy, and both a and b have a copy, respectively.
We can assume G is of unit length, otherwise the offsets and cost functions can be
scaled to obtain the same results. We write the offset functions as a triplet
similarly for the work functions. Suppose the starting state
is a. Then W D;D). The ser and tran functions are given in Table 2. By the
definition of the offset functions, and since it is free to discard a copy of F, we always
have (b), and at least one of ! i (a) and ! i (b) is zero. Without loss of
generality, we assume a starting offset function vector of
after oe i has arrived. Table 3 gives the changes in offsets for different combinations of
requests and offsets in response to the new request oe i+1 .
a b ab
a 0 D D
ab
a r a w b r b w
a
ab

Table
Transition and Service Costs
Case 1:
a r 0 min(k
a w
Case 2:
a r 0 min(1; l) l 0
a

Table
Changes in Offsets
Let s be the current state of R. Our algorithm specifies the new required residence
set, R, after oe i+1 has arrived and the offsets have been updated; it assumes state a is
a zero-offset state.
Algorithm Edge:
D, drop at b, i.e., set
Theorem 3.6. Algorithm DetEdge is strongly 3-competitive.
ON-LINE DISTRIBUTED
Proof. We first show that for each request oe j , \DeltaC Edge
holds, for some function \Phi(\Delta) defined below. Let a be a zero-offset state and we have
any time, we define the potential function:
Initially, and we always have \Phi  0. When can be
considered to be in state a or b, and \Phi(a;
and hold in the following cases:
a r or a w ,
a r or b r .
Our algorithm ensures that \DeltaC Edge = 0 in these cases. Let use show that ( ) holds for
all possible combinations of state, request, and offset. The offsets and state variable
below are the ones before the new request oe i+1 arrives. We consider the k  1 cases;
the are similar to that when k  1 and oe a r or a w .
Case 1: oe
We have \Deltaopt
the last execution of the algorithm, we must have
Case 2: oe
We have \Deltaopt or ab, we
must have
Case 3: oe
We have \Deltaopt 1. In this case \DeltaC Edge  1, \Delta\Phi  2, and L:H:S:( )  3 hold.
Inequality ( ) also holds when DetEdge changes state: when DetEdge moves
from state ab to state a, !
to state ab \Delta\Phi = \Gamma\DeltaC Edge = \GammaD. Hence, ( ) holds for all possible combinations of
offsets, requests, and residence set.
We claim that no deterministic algorithm is better than 3-competitive for FAP
on an edge. For migration, it is known that no deterministic algorithm can be better
than 3-competitive on a single edge [7]. We show that given any on-line algorithm
A for FAP there exists another on-line algorithm A 0 such that (i) CA 0 (oe)  CA (oe)
for any oe with only write requests, and (ii) A 0 always keeps only one copy of F, at
a node in A's residence set, and (iii) whenever A has only one copy of F, A 0 has a
copy at the same node. Since A 0 is a legal algorithm for any instance of the migration
problem, and the optimal cost to process oe without using replications is no less than
the optimal cost with replications, A is c-competitive on write-only sequences only if
A 0 is a c-competitive migration algorithm. This implies the claim.
Algorithm A 0 is obtained from A as follows. Initially, both A and A 0 have a copy
of F at the same node. The following rules are applied whenever A changes state.
(1) If A replicates, A 0 does not change state.
(2) If A migrates, A 0 follows.
(3) If A drops a page, A 0 follows to the same node.
It follows from the rules above that (ii) and (iii) hold, and A 0 cannot incur a write
cost higher than that of A. Each movement of A 0 in (1) or (2) corresponds to a
distinct migration or earlier replication by A, respectively. So A 0 cannot incur a
higher movement cost than A. The claim follows.
J. WESTBROOK, and D. YAN
3.2. An Optimal Deterministic Tree Algorithm. Recall that for each edge
on the tree, request sequence oe induces a sequence oe ab on (a; b). The
tree algorithm is based on factoring into individual edge subproblems and simulating
DetEdge on each subproblem. After r 2 oe is served, for each edge the
induced request r ab is computed and the offset vector for the induced subproblem
is updated. The following algorithm is then executed, updating the residence set,
R(T ree). Initially R(T ree) consists of the single node containing F.
Algorithm Tree:
(1) Examine each edge (u; v) in any order, and simulate the first
step of Algorithm DetEdge in the induced subproblem. If DetEdge
replicates to one of the nodes, say v, in the induced subproblem, then
add v to R(T ree) and replicate to v.
(2) Simulate step 2 of DetEdge for all edges. For any node v, if
the edge algorithm for an incident edge deleting
node v from e's residence set in e's induced problem, mark v.
(3) Drop at all marked nodes.
To show that DetTree is 3-competitive, we will show that it chooses a connected
residence set and for each edge, it induces the state required by DetEdge. This is
not immediately obvious, because the requirements of DetEdge on one edge might
conflict with those on another edge. For example, one edge might want to drop a
copy that another edge has just replicated.
We begin by analyzing the structure of the offset functions in the induced edge
problems. For the rest of this subsection, the offset values and functions for each
refers to that results from the induced sequence oe ab . The next lemma
characterizes the offset distribution between two adjacent edges.
Lemma 3.7. The following properties hold:
(A) At any time, there exists a root node r, such that corresponds to a
zero offset state in the induced problems of all edges.
(B) For any edge (x; y) on the tree, define S i (x;
adjacent edges (x; y) and (y; z), the inequality S i (x; y)  S i (y; z) holds, 8 i.
Following from the earlier definitions (see the beginning of Section 3.2), the claim
(A) above states that there is a node r such that for any edge (a; b) where a is nearer
to r than b, state a is a zero offset state for the edge. Note that the location of the
root node r may not be unique, and its location changes with requests. The lemma
implies the following conditions.
Corollary 3.8.
be an edge in T such that a root r is in T x . Let z 6= x be a neighbor
of y, and edges (x; y) and (y; z) have offsets (0; k xy ; l xy ) and (0; k yz ; l yz ),
respectively. Then
(D) Let (x; y) and (y; z) be adjacent edges with a root r in the subtree that is rooted
at y and formed from removing the two edges from T . Let the offsets in the
edges be (k xy ; 0; l xy ) and (0; k yz ; l yz ), respectively. Then l xy  (l
Proof. (of Lemma 3.7) We use induction on the number of requests. Initially, let
r be the node holding the single copy of F ; all the edges have offset vectors (0; D;D)
and the lemma holds trivially. We assume the lemma holds for
revealed
requests and show that it remains valid after oe t+1 has arrived at a node w. We first
show how to locate a new root. Let P represent the path from r to w. Unless specified
otherwise, the offsets referred to below are the ones before oe t+1 arrives. We choose
the new root, r 0 , using the following procedure.
Procedure FindRoot
(1) If (i) r and all the edges along P have offsets of the
(2) Otherwise, move along P from r toward w, and cross an edge if it has offset
vector of the form (0; 0; l) until we cannot go any further or when w is reached.
Pick the node where we stop as r 0 .
Let us show that r 0 is a valid root for the new offsets. We picture P as a chain of
edges starting from r, going from left to right, ending in w. If the condition in step
(1) of the algorithm is satisfied, oe t+1 corresponds to a request at the zero offset state
for all edges. By Table 3, r remains a valid root node. Suppose (2) above is executed.
For any edge that is not on P, or is on P but is to the right of r 0 , its zero-offset state
remains the same. Node r 0 is a valid root node for these edges. By (C.4), edges along
P with offsets of the form (0; 0; l) must form a connected subpath of P, starting from
r and ending in r 0 . They have the same value for the parameter l. By Table 3, their
offsets change from (0; 0; l) to (1; 0; minfl or (min(1; l); 0; l), and r 0 is a valid
root node for them. Hence (A) holds for our choice of r 0 above.
To show that (B) holds, we consider any two adjacent edges (x; y) and (y; z)
whose removal will divide T into three disjoint subtrees: T x ; T y , and T z , with roots
y, and z, respectively. We show that for different possible positions of r and w, (B)
remains valid after oe t+1 has arrived, i.e., S t+1 (x; y)  S t+1 (y; z) holds when oe t+1 is
a write or a read , when r z . We assume
holds before oe t+1 arrives.
Suppose oe t+1 is a read request, r 2 T x , and w 2 T x . For edge
Condition (B) can be shown to hold in other situations
by a similar case analysis. Please refer to the Appendix for the complete case analysis.
Thus (B) holds for request and the lemma follows.
Theorem 3.9. Algorithm DetTree is strongly 3-competitive.
Proof. We show that DetTree induces DetEdge on each tree edge. The theorem
then follows from Lemmas 3.4 and 3.5 and Theorem 3.6.
We proceed by induction on the number of requests. Initially, R(T ree) consists
a single node. Suppose R(T ree) is connected after the first t 2 Z
for each edge (a; b), the state induced by R(T ree) is equal to the state desired by
DetEdge when run on oe ab . Consider the processing of request t + 1.
Step (1): Replication. We do a subinduction on the number of replications done in
Step (1), and show that no replication is in conflict with the state desired by any
edge.
Suppose that processing edge (a; b) in Step (1) causes F to be replicated to a.
lies in T b , inducing state
from the definition of DetEdge, the definition of the induced subproblem, and the
inductive hypothesis. Let Q be the path from b to the nearest node in R(T ree).
If Q 6= fbg, then, to avoid conflict, each edge along Q must also require replication
across it. From (A) and (C.2) in Theorem 3.7, we see that each edge (x; y) in Q has
12 C. LUND, N. REINGOLD, J. WESTBROOK, and D. YAN
an offset of the form ! is nearer to b than y, and requires a
replication. A similar argument holds for the case when s = a and !
Step (2): Marking Nodes to Drop: Again we perform a subinduction on the number
of markings done in Step (2), and show that no marking is in conflict with the state
desired by any edge and that a connected residence set results.
Suppose that processing edge (a; b) in Step (2) causes b to be marked. This occurs
because (a; b) has !
Since R(T ree) is connected by hypothesis, both a and b are in R(T ree), and the
nodes in T b with a copy of F span a connected subtree of T b , with b as its root. Let
us call it T 0
b . If T 0
b 6= fbg, each edge (x; y) in T 0
b is in state s = xy. By (A) and (C.3)
in Theorem 3.7, (x; y) must have offset nearer to b than y is.
Under DetEdge, (x; y) needs to drop the copy of F in node y. Hence all the nodes
in T 0
b are required to be removed from R(T ree), the new R(T ree) remains connected,
and no edges are in conflict.
Thus R(T ree) is connected, all induced edge algorithms match DetEdge, and
DetTree is 3-competitive.
4. Randomized Algorithms for FAP on a Tree. Our approach to building
a randomized tree algorithm is the same as our approach in the deterministic case.
We give a randomized algorithm for a two-point space, RandEdge, that is based
on counter values assigned at the nodes. By factoring, we obtain from RandEdge a
(2+1=D)-competitive algorithm, RandTree, for file allocation on a tree. RandTree
requires the generation of only O(logD) random bits at the beginning of the algorithm,
after which it runs completely deterministically. It is simpler than the tree algorithm
in [19], which can require the generation
of\Omega\Gamma/29 D) random bits after each request
is served.
4.1. An Optimal Randomized Edge Algorithm, RandEdge. Let edge
(a; b). We maintain counters c a and c b on nodes a and b, respectively. They satisfy
Our algorithm maintains a distribution of R
dependent on the counter values. Initially, the node with a copy of F has counter
value D, and the other node has counter value 0. The counter values change according
to the following rules. On a read request at a, we increment c a if c a ! D. On a write
request at a, if (c a D, we
increment c a . The counters change similarly for a request at b. There is no change in
the counter values in other cases.
Algorithm RandEdge always maintains a distribution of R such that
(1a)
(1c)
Observe that the probability of having a copy of F at node v 2 fa; bg is c v =D.
In order to maintain this distribution, RandEdge simulates D deterministic
algorithms, numbered from 1 to D. The moves of each deterministic algorithm are
constructed (deterministically) on-line, according to rules given below. Before the
first request, one of the D algorithms is picked at random. RandEdge then makes
ON-LINE DISTRIBUTED
the same moves as the chosen deterministic algorithm. Thus p e [s], s 2 fa; b; abg, is
the proportion of algorithms in state s, and the expected cost incurred by RandEdge
is the average of the costs incurred by the D algorithms.
We define the D algorithms that achieve the probability distribution in (1). Suppose
that initially, only node a has a copy of F . Then initially the D algorithms are
placed in state a. The following changes are made after a new request, oe i , has arrived.
Without loss of generality, we assume the request arises at node a. (The c a and c b
values below refer to the counter values just before oe i arrives.)
ffl There is no change in the algorithms if there is no change in the counter
values.
D, the lowest-numbered algorithm in state b
moves to state ab.
ffl Case 2: if oe D, the lowest-numbered algorithm in state ab
moves to state a.
ffl Case 3: if oe D, the lowest-numbered algorithm
in state b moves to state ab.
Lemma 4.1. RandEdge is feasible and maintains the probability distribution in
(1).
Proof. By feasible we mean that whenever a move must be made in Cases 1, 2,
and 3, there is some algorithm available to make the move. The choice of lowest-numbered
algorithm is only to emphasize that the choice must be independent of
which algorithm RandEdge is actually emulating.
The lemma holds initially with c a = D and c We prove the lemma by
induction on the requests, and assume it holds before oe i arrives. If there is no change
in counter values after oe i has arrived, the lemma holds trivially. By the induction
hypothesis, in case 1 above, since c a ! D and p e [b] ? 0, at least one of the D
algorithms is in state b; in case 2, since (c a there is
an algorithm in state ab; in case 3, since c a ! D, there is an algorithm in state b.
Hence, RandEdge is feasible. It can be verified that the changes in the algorithms
implement the probability distribution in (1) for the new counter values.
Theorem 4.2. RandEdge is strongly
Proof. For each node v 2 fa; bg, we maintain the potential function:
D ) OPT has a copy of F at v
D otherwise
where OPT represents the adversary. Let the overall potential function
at any time, \Phi  0. We show that in response to
each request and change of state,
E(\DeltaC RandEdge
(2)
holds, where \DeltaOP T , E[\DeltaC RandEdge ] and E(\DeltaM i ) are the cost incurred by the event
on OPT , and the service and movement costs incurred on RandEdge, respectively.
The c a and c b values below are the counter values just before the new request oe i
arrives.
Case 1: Request oe
If c a = D, inequality (2) holds trivially. Suppose c a ! D. We have
E(\DeltaC RandEdge
14 C. LUND, N. REINGOLD, J. WESTBROOK, and D. YAN
D OPT has a copy of F at a
D otherwise
It follows that if OPT has a copy of F at a when oe i arrives,
otherwise, Inequality (2) holds.
Case 2: Request oe
We have
E(\DeltaC RandEdge
D OPT has a copy of F at b
\Gammac b
D OPT has a copy of F at b
Inequality (2) holds.
Case 3: Request oe
If c a = D, L.H.S.(2)=0 and (2) holds trivially. Suppose c a ! D. We have
E(\DeltaC RandEdge
c a
OPT has a copy of F at a
ae 0 OPT has a copy of F at a
D otherwise
Hence, (2) holds.
Case 4: OPT changes state.
When OPT changes state, E(\DeltaC RandEdge It can be checked from
the definition of \Phi that when OPT replicates, \DeltaOP
when OPT discards a copy of F, \Delta\Phi  0.
Since (2) holds for all possible events, by Theorem 4.6 RandEdge is strongly
4.2. An Optimal Randomized Tree Algorithm-RandTree. We extend
RandEdge to a randomized algorithm for FAP on a tree, T , by means of factoring.
Our algorithm, RandTree, induces RandEdge on each edge for the induced request
sequence for the edge.
Description of Algorithm RandTree. RandTree internally simulates D deterministic
algorithms. Each of them maintains a residence set that spans a subtree
of T . Initially, the residence set for each of them is the single node that contains F.
One of the D simulated algorithms is picked uniformly at random at the beginning,
and RandTree behaves exactly the same as the particular algorithm chosen.
We maintain counters c a and c b for each edge (a; b) in the tree. Using the factoring
approach (see section 3.2), we obtain an induced request sequence oe ab for (a; b). The
counter values change according to the same rules as described in the single edge
case (section 4.1), using oe ab . RandTree responds to each request and maintains an
(induced) distribution as required by RandEdge in (1) for each of the edges.
Read Request. Suppose the new request, oe i , is a read request at a node g. Let
T be rooted at g, and be an edge with a nearer to g than b is. The c a and
c b values described below are the counter values before oe i arrives. The edges can be
classified into three types:
2: edges with c a = D and c b ? 0, and
3: edges with c a ! D.
RandEdge requires no change in probability values for the first two types of edges;
for type 3 edges, it requires p e [b] decreases by 1=D and p e [ab] goes up by 1=D. For
any node v, we use T (v) to denote the subtree of T rooted at v. RandTree changes
the subtree configurations maintained by the D algorithms by using the following
procedure (fig. 1).
(1) Let F be the forest of trees formed by all the type 3 edges.
(2) While there exists a tree T 0 2 F with at least one edge, Do
Let x be a leaf node in T 0 and P be the path from x to the root
node of T 0 .
(The root node of T 0 is the node in T 0 that is nearest to g.)
(2.2) Pick any one of the D algorithms that maintains a subtree, Z,
that includes node x and lies entirely in T (x).
Make that algorithm replicate along P , i.e., replace Z by Z [ P .
Remove the edges in P from T 0 and update the forest F .
Fig. 1. Algorithm RandEdge (Read Requests)
Lemma 4.3. RandTree implements the required changes for all the edges for a
read request.
Proof. We prove the lemmaby induction on the requests. Suppose that RandTree
induces RandEdge on all edges before oe i arrives. Let y be the parent node of x. If
RandTree is feasible, i.e., it can be executed, it implements the changes required by
RandEdge as described above, for all edges. We show that this is the case.
If x is a leaf node of T , since (x; y) is a type 3 edge, p (x;y) [x] ? 0 and one of the
D algorithms must have the single node fxg as its tree configuration.
Otherwise, suppose all the descending edges of x are of type 1. Let (x; w) be one
of them. Then p (x;w) none of the algorithms maintains a subtree
with any edge in T (x). Since p (x;y) [x] ? 0, one of the algorithms must have fxg as
its subtree.
Otherwise, suppose x has descending type 2 edges. Let (x; w) be any one of them.
Thus each of these edges is contained in the
subtree of at least one of the algorithms, and none of the algorithms has its subtree in
T (w). Since p (x;y) [x] ? 0, at least one of these subtrees must lie in T (x) and contains
node x.
Hence, our algorithm is feasible and the lemma holds.
Write Request. Suppose oe We use the same notation as in the read
request case. The edges can be classified into three types:
2: edges with (c a
3: edges with (c a
J. WESTBROOK, and D. YAN
RandEdge requires no change in probability values for the type 3 edges; for type 1
edges, it requires p e [ab] decreases by 1=D and p e [a] increases by the same amount;
decreases by 1=D and p e [ab] increases by the same
amount. RandTree performs the following (fig. 2).
(1) Let F be the forest of trees formed by all the type 1 edges.
(2) While there exists a tree T 0 2 F with at least one edge, Do
0 be the root node of T 0 and x be one of its children nodes in
(2.2) Pick an algorithm that has a subtree Z that includes edge (g
If Z is contained in T 0 , make the algorithm replace Z by the single-node
replace Z by the tree formed by
edges in (Z \Gamma T 0 ).
Replace T 0 in F by the subtrees formed by T
(3) Let F be the forest of trees formed by all the type 2 edges.
(4) While there exists a tree T 0 2 F with at least one edge, Do
(4.1) Let x be a leaf node of T 0 and P be the path from x to the root
node of T 0 .
(4.2) Pick any one of the D algorithms that maintains a subtree, Z,
that includes node x and lies entirely in T (x).
Make that algorithm replicates along P , i.e., extends Z to Z [P .
(4.3) Remove the edges in P from T 0 and update the forest F .
Fig. 2. Algorithm RandEdge (Write Requests)
Lemma 4.4. RandTree implements the required changes for all the edges for a
request.
Proof. We prove by induction and assume RandEdge is induced on all the edges
before oe i arrives. If RandTree is feasible, it implements the required changes for all
the edges. We show that this is the case.
Consider the first loop of the algorithm (in step (2)). Since p (g 0 ;x) [g 0 x] ? 0, subtree
Z must exist. RandTree removes edges from Z that are contained in T 0 . Note that
the p e [ab] values for type 2 and 3 edges are zero; RandTree processes edges in T 0 in
a top-down fashion, and configuration connected subtree. Thus
the first loop can be executed.
Consider the second loop of the algorithm (in step (4)). Let y be a parent node
of x. Then p (x;y) x is a leaf node in T , one of the
D algorithms must have fxg as its subtree. If x has a descending type 1 edge, by
the first part of the algorithm, one of the D algorithms must have fxg as its subtree
after running the first loop of the algorithm. Suppose all the descending edges of x
are type 3 edges. Let (x; w) be a type 3 edge; then p (x;w)
one of the algorithms must have fxg as its subtree.
Hence, the algorithm is feasible and the lemma follows.
Lemmas 4.3 and 4.4 imply that RandTree induces RandEdge on all the edges.
Theorem 4.5 follows from the above lemmas and Theorem 4.2.
Theorem 4.5. Algorithm RandTree is strongly 1=D)-competitive for FAP
on a tree against an oblivious adversary.
4.3. Lower Bound. We show that the competitive ratio,
above is the best possible for file allocation against an oblivious adversary, even if G
is a single edge.
Theorem 4.6. No on-line algorithm for the file allocation problem on two points
(a; b) is c-competitive, for any c ! (2
Proof. Let A be any randomized algorithm for the file allocation problem on two
points. We define a potential function \Psi, and give a strategy for generating adversary
request sequences such that:
(i) for any C there is a request sequence oe with optimum cost  C;
(ii) the cost to RandEdge on oe is at least (2
independent of oe;
(iii) \Psi is bounded; and
(iv) for each request generated by this adversary,
If conditions (ii), (iii), and (iv) hold for an adversary sequence oe, then summing
(3) over the sequence gives
where B is bounded. By condition (i), the adversary can make OPT (oe) arbitrarily
large, so there is no constant B 0 independent of oe such that CA
OPT (oe) +B 0 . Hence A cannot be c-competitive for c
We now define the adversary's strategy. We assume that both the on-line and
off-line algorithms start with a single copy of F at a. Our adversary will only generate
requests that result in offset functions of the form (0; zero-cost
self-loop is a request such that the offset function is unchanged and \Deltaopt = 0. By
a theorem of [18], there is always an optimal on-line algorithm that incurs 0 expected
cost on a zero-cost self loop. We assume A has this property. This simplifies the
adversary's strategy, although the result can still be proved without this assumption.
Suppose that the current offset function is (0; i; i), and let p i be probability that
RandEdge is in state a. Suppose A is in state a with probability q. If q ! p i the
adversary requests a w , otherwise the adversary requests b r . When
have zero-cost self-loop if and so the adversary will request
b r . Similarly, when (a r is a zero-cost self-loop) and the adversary
requests a w . Therefore the adversary can always generate a next request using the
above rules, and the request sequence can be made arbitrarily long. Since there are
only D offset functions that can be generated by this strategy, an arbitrarily long
sequence of requests must cycle through the offset functions arbitrarily often. Notice,
however, that the only cycles which cost OPT nothing are zero-cost self-loops. Since
the adversary never uses these requests, all cycles have non-zero cost, so by continuing
long enough the adversary can generate request sequences of arbitrarily large optimum
costs. Hence condition (i) hold.
Next we consider condition (ii). Recall c a and c b , the counter values maintained
by RandEdge. We claim that if the offset function is (0;
This is true initially, when F is located only at a, and D. By inspection
of RandEdge one can verify that the whenever the adversary generates request b r ,
c b increases by 1, and that whenever the adversary generates a w , c b decreases by 1.
Hence and the expected movement cost incurred by RandEdge is 1 on b r
and 0 on a w . With reference to the proof of Theorem 4.2, note that the amortized
cost to RandEdge is exactly 2+1=D times the cost to OPT on any request that the
adversary might generate, assuming OPT does not move following the request. (The
adversary never generates b r if c or a w if c 0.) The amortized cost incurred
J. WESTBROOK, and D. YAN
by RandEdge is therefore exactly 2+1=D times the cost incurred by an "optimum"
algorithm that only ever has a copy of F at a. It is possible to show that this cost
really is optimum for our sequences, but in any case it is certainly lower-bounded by
the true optimum cost, and so (ii) holds.
Now define \Psi to be D \Delta maxf0; g. This is trivially bounded by 1, so (iii)
holds. Finally, we must verify (3).
Case 1: The adversary requests a w .
In this case the new offset function must be 1). Suppose that after
the request A has mass q 0 at a. Then \DeltaC
Case 2: The adversary requests b r .
In this case the new offset function must be (0; 1). Suppose that after the
request A has mass q 0 at a. Then \DeltaC
5. Migration on a Uniform Network. We give a 1=(2D))-competitive
randomized algorithm against an oblivious adversary for migration on a uniform net-
work. This competitive ratio is optimal even for a single edge [10]. Let G be a
complete graph on n nodes labeled 1 to n. Initially, only node 1 has a copy of F.
Our algorithm is based on the offsets calculated on-line. Let ng and the
algorithm is in state s if the single copy of F is at node s. We have the cost functions
ae
ae
D otherwise
and initially W
Suppose the ith request is served and the new offset for each node, s, is calculated.
Algorithm Migrate: The algorithm maintains a probability distribution such that
the probability, p[s], that a node, s, contains F is as follows:
After a new request has arrived, our algorithm moves to different states with transition
probabilities that minimize the total expected movement cost, while maintaining the
new required distribution.
Theorem 5.1. Given any oe, the expected cost incurred by Migrate, E[C mig (oe)],
satisfies
Proof. We show that after a request has arrived,
holds, where E[\DeltaC mig ] is the expected cost incurred by Migrate, E[\DeltaM ] is the
expected movement cost, \Delta\Phi is the change in the potential function:
vs
Initially, any time, since at least one v
An offset table similar to Table 3 for file allocation can be constructed. Since
migration is equivalent to FAP with only write requests, it can be seen that if request
oe i+1 is at a node s with the offsets for all other states
will increase by one, subject to a maximum of D, and \Deltaopt is at
a node s with the offset for state s will decrease by one, all other offsets
remain the same, and \Deltaopt
Case 1: A request at s such that v s ! D.
In this case, we have \Deltaopt increases by one.
If s  k then E[\DeltaC mig It can be verified that E[\DeltaM ]  1=2,
\Delta\Phi
then the movement cost is zero. We also have E[\DeltaC mig
Case 2: A request at s such that v
We have \Deltaopt decreases by 1. Each
such to \Delta\Phi, and no more than 1=2 to E[\DeltaM ]. We
have s is the probability mass at s, and
Hence
6. Replication. We give upper and lower bounds on the performance of randomized
on-line algorithms for the replication problem.
20 C. LUND, N. REINGOLD, J. WESTBROOK, and D. YAN
6.1. Randomized On-Line Algorithms. Let e
e D =(e D \Gamma 1). So fi D \Gamma!e=(e \Gamma 1)  1:58 as D\Gamma!1. We describe randomized algorithms
that are fi D-competitive against an oblivious adversary on the uniform network
and trees. First, consider a single edge (r; b) of unit length. Initially, only r contains
a copy of F . Suppose algorithm A is ff-competitive, and it replicates F to node b with
probability after the ith request at b, where
1. The p i 's and ff must satisfy,
for each k 2 Z
is the expected cost incurred by A when oe contains k requests at b. The optimal
off-line strategy is to replicate a copy of F to b before the first request arrives if
k  D, and does not replicate otherwise. Algorithm A incurs a cost of (D
replicates right after serving the ith request, i  k; otherwise it incurs a cost of k.
An optimal randomized algorithm is given by a set of p i values that satisfy the above
inequalities for all k, such that ff is minimized. We note that the conditions above
are identical to those for the on-line block snoopy caching problem on two caches in
[15]. Karlin et al. [15] showed that the optimal ff value is fi D . This is achieved when
are zero. The above single
edge algorithm can be applied to a uniform network by replicating F to each node v
after the ith request at v, with a probability of p i - another example of factoring.
Theorem 6.1. There exists a randomized algorithm that is strongly fi D -competitive
against an oblivious adversary for replication on a uniform network.
We can extend the single edge algorithm to a tree, T , rooted at r, the node that
contains F initially. The algorithm only responds to requests at nodes not in the
current residence set.
Algorithm TREE: Keep a counter c i on each node i 6= r. Initially,
all request arrives at a node x, and w is the node
nearest to x that contains a copy of F . After serving the request, the
counters for all the nodes along the path from w to x are increased
by one. Let the nodes along the path be
Perform the following procedure each time after a request has been
served:
1.
(2) For
, replicate to node i j from node i j \Gamma1 .
(2.2) If F is not replicated to i j , STOP.
Theorem 6.2. Algorithm TREE is strongly fi D -competitive against an oblivious
adversary for replication on a tree network.
Proof. Without loss of generality, we assume that a connected R is always maintained
by any solution. Let x 6= r be any node and y its parent. Before x obtains a
copy of F , a cost equal to the weight of (x; y) is incurred on the edge for each request
at a node in the subtree rooted at x. (This follows because R is connected and the
unique path from x to r passes through (x; y).) By our single edge algorithm, the
algorithm TREE is fi D -competitive if, for each node x 6= r, a copy of F is replicated
to x after the ith request at the subtree rooted at x, with a probability p i . It can be
shown by induction on the requests that before x acquires a copy of F, the counter
on x records the number of requests that have arrived at the subtree rooted at x,
and these counters form a non-increasing sequence on any path moving away from
r. Hence, the values p c i j
are defined
probability values. It is simple to verify that each time a node at the subtree rooted
at x receives a request, a copy of F is replicated to x with probability p cx , where c x
is x's new counter value. The theorem follows.
6.2. Lower Bound. We show that no randomized algorithm can be better than
2-competitive against an adaptive on-line adversary. We use n to denote the number
of nodes in G.
Theorem 6.3. Let ffl be any positive function of n and D, taking values between
0 and 1. No on-line algorithm is better than n))-competitive for replication
against an adaptive on-line adversary.
Proof. Let node a have the initial copy of F and let (a; b) be any edge in G.
Let A be any on-line algorithm which replicates to b after the jth request at b with
probability . The adversary issues requests at b until A replicates or
have been issued, whichever first happens. Algorithm A incurs an
expected cost of
We choose different N " 's for two different cases.
Suppose
" be the minimum positive integer that is greater
than D and such that
Given D, parameter N " is a finite and unique
constant. The adversary replicates to b before the first request arrives, incurring a
cost of D. From equation (5), we have E[CA (oe)]  D
giving a
ratio of at least 2.
Suppose
D). The adversary does not replicate and
incurs an expected cost of
?From (5), we have
(7a)
Given the p j 's, one can choose N '' so that
arbitrarily close to 1. Since
the series
one can also choose N " so that
arbitrarily close to zero. Thus, by comparing (6) and (7b), we see that given any ",
one can choose a finite N " so that the ratio is as close to
22 C. LUND, N. REINGOLD, J. WESTBROOK, and D. YAN
7. Off-Line Replication and File Allocation. We show that the off-line replication
problem is NP-hard, and the off-line file allocation problem on the uniform
network can be solved in polynomial time.
7.1. The Off-Line Replication Problem. Awerbuch et al. find interesting
relationships between the on-line Steiner tree problem [14, 23] and on-line FAP. We
show that the (off-line) replication problem is NP-hard by using a straight-forward
reduction from the Steiner tree problem [12, 16] (see Section 2 for the definition).
The proof involves creating an instance for the replication problem in which (D
requests are issued at each of the terminal nodes for the Steiner tree problem instance,
forcing the optimal algorithm to replicate to these nodes.
Theorem 7.1. The replication problem is NP-hard, even if G is is bipartite and
unweighted, or if G is planar.
7.2. Off-line Solution For File Allocation on a Uniform Network. We
show that the off-line file allocation problem on a uniform network can be solved in
polynomial time by reducing it to a min-cost max-flow problem. A similar reduction
was obtained by Chrobak et al. [8] for the k-server problem. We convert an instance
of the FAP on a uniform network on nodes min-cost max-flow problem
on an acyclic layered network, N , with O(n \Delta joej) nodes and O(n 2 joej) arcs. Initially
node 1 has a copy of F. An integral maximum flow in N defines a dynamic allocation
of F in the uniform network. The arcs costs in N are chosen so that the min-cost
max-flow in N incurs a cost differs from the minimum cost for FAP on the uniform
network by a constant. Network N is constructed as follows:
Nodes: Network N has (joej layers of nodes, nodes in each layer, a
source node s and a sink node t. Layer k, 0  k  joej, has nodes fv k
n g and
(n\Gamma1) g. Each node allows a maximum flow of one unit into and out of it. The
nodes correspond to the nodes in the uniform network. Layer k of N corresponds
to the state of the uniform network after oe k has been served.
Arcs: There is an arc going from each layer k node to each layer
there is an arc from each layer joej node to t, arc (s; v 0
(s;
1). All the arcs have unit capacity.
A Flow: A maximum flow in N has a value of n. Given integer arc costs, there is a
min-cost max-flow solution with only an integral flow of either 0 or 1 in each arc. A
flow of 1 into a v k
j represents the presence of a copy of F at node j just before request
arrives. If the flow comes from a v (k\Gamma1)
represents a copy of F being moved from
node i to node j after serving the 1)st request; if the flow comes from a u (k\Gamma1)
represents a replication to node j. A flow from a v (k\Gamma1)
j to a u k
w represents the copy of
F at j is dropped after oe (k\Gamma1) is served. Thus an integral flow in N defines a strategy
for relocating copies of F. Since there are (n \Gamma 1) u nodes in each layer, an integral
max-flow must include a flow of 1 unit into at least one of the v nodes in each layer.
This corresponds to the requirement that there is always at least a copy of F in the
uniform network.
Edge Costs: Edge costs are chosen so that the optimal flow has cost equal to the
optimal off-line cost for FAP minus the number of read requests, J , in oe. Arcs with
one end point at s or t have zero costs. Let (a; b) be any other arc, going between
layer k and (k+1). Its cost is equal to the sum of its associated movement and service
costs. Suppose b is v (k+1)
. Then (a; b)'s associated movement cost is D unless a is
. If oe (k+1) is a write at some node other than node i, the service cost is
is a read at node i, the service cost is \Gamma1. The costs for all other cases are zero. The
movement and service costs account for the cost for replication and serving requests,
except a node is charged \Gamma1 when a read request arrives and it has a copy of F . If we
add J to the cost of the optimal flow, thus charging each read request 1 in advance,
the sum is equal to the cost of an optimal dynamic allocation of F.
Using the algorithm in [21] for solving the min-cost max-flow problem on acyclic
networks, FAP on a uniform network can be solved in polynomial time.
Theorem 7.2. An optimal (off-line) file allocation on a uniform network can be
found in O(n 3
8. Open Problems. Interesting open problems include finding a strongly competitive
randomized algorithm for FAP on a uniform network. Awerbuch et al. [2]
conjecture that if there exists a c n -competitive algorithm for the on-line Steiner tree
problem [14, 23], then there exists a O(cn)-competitive deterministic algorithm for
FAP. This conjecture is still open. For the migration problem, there is a gap between
the best known bounds [4, 10].



--R


Competitive Distributed File Allocation
Dynamic File Migration in Distributed Computer Systems
On Page Migration and Other Relaxed Task Systems
Competitive Algorithms for Distributed Data Manage- ment
On the Power of Randomization in Online Algorithms
Competitive Algorithms for Replication and Migration Prob- lems
New Results on Server Prob- lems
The Server Problem and On-line Games
Page Migration Algorithms Using Work Functions
Comparative Models of The File Assignment Problem
The Rectilinear Steiner Tree Problem is NP-complete

Dynamic Steiner Tree Problem
Competitive Randomized Algorithms for Non-Uniform Problems
Reducibility Among Combinatorial Problems
Randomized On-line Algorithms for the Page Replication Problem
Linear Programs for Randomized On-Line Algorithms

Randomized Competitive Algorithms for
Data Structures and Network Algorithms
Randomized Algorithms for Multiprocessor Page Migration
The Performance of Greedy Algorithms for the On-Line Steiner Tree and Related Problems
Steiner Problem in Networks: A Survey
--TR

--CTR
Baruch Awerbuch , Yossi Azar , Yair Bartal, On-line generalized Steiner problem, Theoretical Computer Science, v.324 n.2-3, p.313-324, 20 September 2004
memory management;data management;competitive analysis;on-line algorithms