Online hierarchical cooperative caching.
We address a hierarchical generalization of the well-known disk paging problem. In the hierarchical cooperative caching problem, a set of n machines residing in an ultrametric space cooperate with one another to satisfy a sequence of read requests to a collection of (read-only) files. A seminal result in the area of competitive analysis states that LRU (the widely-used deterministic online paging algorithm based on the "least recently used" eviction policy) is constant-competitive if it is given a constant-factor blowup in capacity over the offline algorithm. Does such a constant-competitive deterministic algorithm (with a constant-factor blowup in the machine capacities) exist for the hierarchical cooperative caching problem? The main contribution of the present paper is to answer this question in the negative. More specifically, we establish an (log log n) lower bound on the competitive ratio of any online hierarchical cooperative caching algorithm with capacity blowup O((log n)1-), where  denotes an arbitrarily small positive constant.
INTRODUCTION
The traditional paging problem, which has been extensively
studied, is defined as follows. Given a cache and a
sequence of requests for files of uniform sizes, a system has
to satisfy the requests one by one. If the file f being requested
is in the cache, then no cost is incurred; otherwise
a uniform retrieval cost is incurred to place f in the cache.
If need be, some files, determined by an online caching algorithm
that does not know the future request sequence, are
evicted to make room for f . The objective is to minimize the
total retrieval cost by wisely choosing which files to evict.
The cost of the online algorithm is compared against that of
an optimal o#ine algorithm (OPT) that has full knowledge
of the request sequence. Following Sleator and Tarjan [10],
we call an online algorithm c-competitive if its cost is at
most c times that of OPT for any request sequence. It is
well-known that an optimal o#ine strategy is to evict the
file that will be requested furthest in the future.
The paging problem is also known as caching if the files
have nonuniform size and retrieval cost. In their seminal
paper, Sleator and Tarjan [10] have shown that LRU (Least-
Recently-Used) and several other deterministic paging algorithms
are k
-competitive, where k is the cache space
used by LRU and h is that used by OPT. They have also
shown that k
k-h+1 is the best possible among all deterministic
algorithms. We call k
h the capacity blowup of LRU. For
files of nonuniform size and retrieval cost, Young [13] has
proposed the Landlord algorithm and shown that Landlord
is k
k-h+1 -competitive. As stated in [13], the focus of
Landlord "is on simple local caching strategies, rather than
distributed strategies in which caches cooperate to cache
pages across a network".
In cooperative caching [6], a set of caches cooperate in
serving requests for each other and in making caching deci-
sions. The benefits of cooperative caching have been supported
by several studies. For example, the Harvest cache [5]
introduce the notion of a hierarchical arrangements of caches.
Harvest uses the Internet Cache Protocol [12] to support discovery
and retrieval of documents from other caches. The
Harvest project later became the public domain Squid cache
system [11]. Adaptive Web Caching [14] builds a mesh
of overlapping multicast trees; the popular files are pulled
down towards their users from their origin server. In local-area
network environments, the xFS system [1] utilizes co-operative
caches to obtain a serverless file system.
A cooperative caching scheme can be roughly divided into
three components: placement, which determines where to
place copies of files, search, which directs each request to
an appropriate copy of the requested file, and consistency,
which maintains the desired level of consistency among the
various copies of a file. In this paper, we study the placement
problem, and we assume that a separate mechanism enables
a cache to locate a nearest copy of a file, free of cost, and
we assume that files are read-only (i.e., copies of a file are
always consistent). We focus on a class of networks called
hierarchical networks, the precise definition of which is given
in Section 2, and we call the cooperative caching problem
in such networks the hierarchical cooperative caching (HCC)
problem.
Our notion of a hierarchical network is constant-factor
related to the notion of hierarchically well-separated tree
metrics, as introduced by Bartal [3]. Refining earlier results
by Bartal [3], Fakcharoenphol et al. [7] have shown that any
metric space can be approximated by well-separated tree
metrics with a logarithmic distortion. Hence, many results
for tree metrics imply corresponding results for arbitrary
metric spaces with an additional logarithmic factor.
If the access frequency of each file at each cache is known
in advance, Korupolu et al. [9] have provided both exact
and approximation algorithms that minimize the average
retrieval cost. In practice, such access frequencies are often
unknown or are too expensive to track. Since LRU
and Landlord provide constant competitiveness for a single
cache, it is natural to ask whether there exists a deterministic
constant-competitive algorithm (with constant capacity
blowup) for the hierarchical cooperative caching problem.
In this paper, we answer this question in the negative.
We show
log n) is a lower bound on the competitive
ratio of any deterministic online algorithm with capacity
blowup O((log n) 1-# ), where n is the number of caches in the
hierarchy and # is an arbitrarily small positive constant. In
particular, we construct a hierarchy with a su#ciently large
depth and show that an adversary can generate an arbitrarily
long request sequence such that the online algorithm
incurs a
cost#t1 log n) times that of the adversary. In-
terestingly, the o#ine algorithms associated with our lower
bound argument do not replicate files.
On the other hand, if an online algorithm is given a sufficiently
large capacity blowup, then constant competitiveness
can be easily achieved. Appendix A shows a result
that, given O(d) capacity blowup, where d is the depth of
the hierarchy (i.e., n)), an LRU-like online algorithm
is constant-competitive. Note that in terms of d,
our lower bound result yields that if the capacity blow up is
O(d 1-# ), then the competitive ratio
d). Hence, our
results imply that there is a very small range of values of the
capacity blowup that separates the regions where constant
competitiveness is achievable and unachievable.
Drawing an analogy to traditional caching, where LRU
and Landlord provide constant competitiveness, we may
think that a constant-competitive algorithm exists for HCC,
being perhaps a hierarchical variant of LRU or Landlord.
In fact, we began our investigation by searching for such an
algorithm. Since the HCC problem generalizes the paging
problem, we cannot hope to achieve constant competiveness
without at least a constant capacity blowup. (In this regard,
we remark that the results of [9] are incomparable as they
do not require a capacity blowup.)
Several paging problems (e.g., distributed paging, file mi-
gration, and file allocation) have been considered in the lit-
erature, some of which are related to the HCC problem.
(See, e.g., the survey paper by Bartal [4] for the definitions
of these problems.) In particular, the HCC problem can be
formulated as the read-only version of the distributed paging
problem on ultrametrics. And the HCC problem without
replication is a special case of the constrained file migration
problem where accessing and migrating a file has the same
cost. Most existing work on these problems focuses on upper
bound results, and lower bound results only apply to
algorithms without a capacity blowup. For example, for the
distributed paging problem, Awerbuch et al. [2] have shown
that, given polylog(n, #) capacity blowup, there exists deterministic
polylog(n, #)-competitive algorithms on general
networks, where # is the normalized diameter of the net-
work. For the constrained file migration problem, Bartal [3]
has given a deterministic upper bound of # m), where m is
the total size of the caches, and a randomized lower bound of
#55 m) in some network topology, and an O(log m log 2 n)
randomized upper bound for arbitrary network topologies.
Using the recent result of Fakcharoenphol et al. [7], the last
upper bound can be improved to O(log m log n).
The rest of this paper is organized as follows. Section 2
gives the preliminaries of the problem. Sections 3 and 4
present the main result of our paper, a lower bound for constant
capacity blowup. Section 5 provides some concluding
remarks. Appendix A presents an upper bound for su#-
ciently large capacity blowup.
2. PRELIMINARIES
In this section we formally define the HCC problem. We
are given a fixed six-tuple
where F is a set of files, C a set of caches, dist a function
from C-C to N, size a function from F to N, cap a function
from C to N, penalty a function from F to N, and N denotes
nonnegative integers. We assume that dist is an ultrametric
(defined below) over C, and we assume that for every
file f in F , penalty(f) # diam(C), where diam(U) denotes
maxu,v#U dist(u, v) for every set of caches U .
2.1 Ultrametrics and Hierarchical Networks
A distance function d : C - C # N is defined to be a
metric if d is nonnegative, symmetric, satisfies the triangle
inequality, and d(u, only if
is a special case of a metric that satisfy the inequality
which subsumes the triangle
inequality
An equivalent and perhaps more intuitive characterization
of our ultrametric assumption is that the caches in C form
a "hierarchical tree", or simply, a tree, defined as follows.
Every leaf node of the tree corresponds to a (distinct) cache.
Every node in the tree has an associated nonnegative value,
called the diameter of the node, such that for every two
caches u and v, dist(u, v) equals the diameter of the least
common ancestor of u and v.
Since a hierarchical network has a natural correspondence
to a tree, in the rest of this paper, we use tree terminology
to develop our algorithms and analysis. In what follows,
the definitions of ancestor, descendant, parent, and children
follow the standard tree terminology. We use T to denote
the tree of caches and we use root to denote the root of T .
The depth of root is 0, and the depth of T is the maximum
depth of any of its nodes. The capacity of a node is the total
capacity of all the caches within the subtree rooted at that
node. We impose an arbitrary order on the children of every
internal node.
2.2 The HCC Problem
The goal of an HCC algorithm is to minimize the total
cost incurred in the movement of files to serve a sequence of
requests while respecting capacity constraints at each cache.
To facilitate a formal definition of the problem, we introduce
additional definitions below.
A copy is a pair (u, f) where u is a cache and f is a file.
A set of copies is called a placement. If (u, f) belongs to a
placement P, we say that a copy of f is placed at u in P. A
placement P is b-feasible if the total size of the files placed
in any cache is at most b times the capacity of the cache.
A 1-feasible placement is simply referred to as a feasible
placement.
Given a placement P, upon a request for a file f at a cache
u, an algorithm incurs an access cost to serve the request.
If P places at least one copy of f in any of the caches, then
the cost is defined to be size(f) - dist(u, v), where v is the
closest cache at which a copy of f is placed; otherwise the
cost is defined to be penalty(f ). After serving a request, an
algorithm may modify its placement via an arbitrarily long
sequence of the following two operations: (1) it may add any
copy to P and incur an access cost as defined above, or (2)
it may remove any copy from P and incur no cost.
Given a capacity blowup of b, the goal of an HCC algorithm
is to maintain a b-feasible placement such that the
total cost is minimized.
3. THE LOWER BOUND
In this section, we show that, given any constant capacity
blowup b, the competitive ratio of any online HCC algorith

is#85 d), where d is the depth of the hierarchy. We
prove this lower bound algorithm by showing the existence
of a suitable hierarchy, a set of files, a request sequence,
and a feasible o#ine HCC algorithm that incurs
d)
factor lower cost for that request sequence than any online
b-feasible HCC algorithm. This result easily extends to analyzing
how the lower bound on the competitive ratio varies as
a function of nonconstant capacity blowup up to the depth
of the hierarchy. In particular, with a capacity blowup of
d 1-# for a fixed # > 0, the competitive ratio of any online
HCC algorithm is still #ill d).
We present an adversarial argument for the lower bound.
Let ON denote a b-feasible online HCC algorithm and ADV
an adversarial o#ine feasible HCC algorithm. ON chooses
a fixed value for the capacity blowup b, and ADV subsequently
chooses an instance of an HCC problem (i.e., the
six-tuple as introduced in Section 2) as follows. The (hi-
erarchy) tree consists of n unit-sized caches that form the
leaves of a regular k-ary tree with depth
for a given choice of k, . The set of files consist of
unit-sized files. The diameter of every leaf node (i.e.,
cache) is 0. The diameter of each node at depth 4bk - 1
is 1, and the diameter of every internal node is at least #
times the diameter of any child, where # > 1. For any file
f , penalty(f) is at least # - diam(root ). Given an instance of
an HCC problem as described in Section 2, we give a program
that takes ON as an input and generates a request
sequence and an o#ine HCC algorithm OFF that incurs a
d) less cost than ON.
At a high level, ON's lack of future knowledge empowers
ADV to play a game analogous to a shell game 1 . In this
game, OFF maintains a compact placement of files tailored
for the request sequence that ADV generates, while ON
is forced to guess OFF's placement and incurs relocation
costs if it guesses incorrectly. When ON finally zeroes in
on OFF's placement, OFF switches its placement around,
incurring a small fraction of the relocation cost that ON has
already expended, and repeats the game.
As an example, consider a simple two-level hierarchy associated
with equal-sized departments within a university. A
set of files, say A, are of university-wide interest, while the
remaining files are of department-specific interest. The capacity
constraints are set up in such a way that a department
can either cache files of its interest or of the university's, but
not both sets simultaneously. OFF stores all the files in A
in an "idle" department, i.e., one with no access activity. On
the other hand, ON has to guess the identity of the idle de-
partment. If ON guesses incorrectly, ADV creates requests
that force ON to move files in A to a di#erent department.
The best strategy for ON is to evenly distribute files in A
across all departments that have not yet been exposed as
nonidle. Unfortunately, even with this strategy ON ends up
incurring a significantly higher cost than OFF. Of course,
in this simplistic case, ON can circumvent its predicament
simply by a two-fold blowup in capacity and using the algorithm
described in the Appendix A. In the rest of the paper,
we present a formalization of the shell-game-like adversarial
strategy and an extension of this strategy to hierarchies of
nonconstant depth.
3.1 The Adversary Algorithm ADV
We fix d disjoint sets of files S0 , S1 , . , Sd such that
|Sd d. We call i the
depth of a file f if f # S i . We define the function g(i, j),
ADV is shown in Figure 1 and the key notations used in
the algorithm (and the rest of the paper) are explained in

Table

3.1. In ADV, the nonnegative integer N specifies the
number of requests to be generated. The code in Figure 1
only shows how ADV generates a bad request sequence for
ON. In Section 4, we show how to augment this code to
obtain an o#ine algorithm that serves the same request sequence
but incurs a much lower cost.
For every node, ADV maintains two integer fields, x and
y, to summarize the state of ON. In ADV, # is a global
variable that records the current node where ADV generates
the next request. Initially, # is set to root . The program
proceeds in rounds. At the end of each round, the algorithm
generates a request. Based on ON's adjustment of its own
placement, ADV adjusts # using the up loop and the down
loop. The former moves # to an ancestor while the latter
moves it to a descendant.
played especially with three walnut shells.
Notation Meaning
#.parent the parent of #
#.anc the ancestors of #
#.desc the descendants of #
#.depth the depth of #
#.diam the diameter of #
#.files
#.cap the total capacity (with no blowup) of the caches in #
#.ch children hierarchies of #
#.placed the set of (distinct) files placed in the caches in # by ON
#.load the number of files f in #.placed such that the depth of f is less than #.depth
#.missing the set of files f such that the depth of f is #.depth but f /
#.placed
#.act g(#.depth , r), where the "activation" value
#.react g(#.depth , k), the "reactivation" value
#.deact g(#.depth , 2k), the "deactivation" value

Table

1: Key notations.
{initially,
1 while count < N do {main loop}
while #.load < #.deact do {up loop}
4 for every child # of #, set both #.x and #.y to 0;
5 #.parent
6 od; {end of up loop}
7 while #.missing = # do {down loop}
8 if a child # of # satisfies #.x > 0 #.load #.react then
else
if # has exactly one child with x equal to 0 then
12 for every child # of #, set both #.x and #.y to 0
child # of # such that
set both #.x and #.y to #.act
17 od; {end of down loop}
generate a request for an element in #.missing at an arbitrary cache in #;
19 ON serves the request and arbitrarily updates its placement;
count := count
od {end of main loop}

Figure

1: The ADV algorithm.
3.2 Correctness of ADV
We show in this section that ADV is well-defined (i.e.,
root just before line 5, # is not a leaf just before line
8, and line 14 finds a child) and that each round terminates
with the generation of a request. For the sake of brevity, in
our reasoning below, we call a predicate a global invariant
if it holds everywhere in ADV (i.e., it holds initially and it
holds between any two adjacent lines of the pseudocode in

Figure

1).
Lemma 3.1. Let I1 denote that every internal node has
a child with the x field equal to 0, I2 denote that # is an
internal node, and I3 denote that #.load #.deact . Then
I1 # I2 is a global invariant and I3 holds everywhere in the
loop.
Proof. The predicate I1 # I2 holds initially because
root and #, and I3 holds just before the down
loop due to the guard of the up loop. We next show that
every line of code out of the down loop preserves I1 #I2 (i.e.,
if I1 # I2 holds before the line, then it holds after the line)
and every line of code in the down loop preserves I1 #I2 #I3 .
Every line of code out of the down loop preserves I1 because
none assigns a nonzero value to a x field. The only line
that a#ects I2 is line 5. We observe that #= root just before
line 5, due to the guard of the up loop and the observation
that root .load # root .deact = 0. Hence, line 5 preserves I2 .
In the down loop, the only line that a#ects I1 is 15, but I3
and the inner if statement establish that # has at least two
children with the x field equal to 0 just before line 14. Hence,
line 15 preserves I1 . The only lines that a#ect I2 are lines 9
and 14. We first observe that just before line 8, #.depth <
4bk - 1. This is because I2 states that #.depth < 4bk and I3
implies that if #.depth
4 . Since #.load is an integer, this implies that #.load #
bk, which implies that #.missing # S 4bk #, a contradiction
to the guard of the down loop. Hence, #.depth < 4bk-1 just
before line 8. Therefore, line 9 preserves I2 . We now show
that line 14 also preserves I2 . Let
{#.ch #.x > 0}. Let r denote |A| and
denote #.depth . We observe that
#A
#.load
#A
#.load -
#.load
#.load
#.deact
#.react
(In the derivation above, the second equality is due to the
guard of the down loop and the definition of load , and the
first inequality is due to the guard of the outer if statement.)
Hence, by an averaging argument, there exists a child # of
# such that
#.load
#.act .
Hence, line 14 finds a child. And as shown above, #.depth <
just before line 8. Hence, line 14 preserves I2 .
The only lines that a#ect I3 are 9 and 14. Both of these
lines preserve I3 because by definition, #.act #.deact and
#.react #.deact for all #.
The claim of the lemma then follows.
Lemma 3.2. The up loop terminates.
Proof. Every iteration of the up loop moves # to its
parent, and root .load # root .deact by definition. Hence, the
up loop terminates.
Lemma 3.3. The down loop terminates.
Proof. Every iteration of the down loop moves # to one
of its children. By I2 of Lemma 3.1, # is always an internal
node. Hence, the down loop terminates.
Lemma 3.4. ADV terminates after generating a sequence
of N requests.
Proof. Follows from Lemmas 3.2 and 3.3.
4. COST ACCOUNTING
In this section, we show that there exists an o#ine HCC
algorithm OFF that serves the sequence of requests generated
by ADV and incurs a cost that is a
log d
less
than that incurred by any b-feasible online HCC algorithm.
4.1 Some Properties of ADV
We first prove some properties of ADV that follow directly
from its structure. For the sake of brevity, for a property
that is a global invariant, we sometimes only state the property
but omit stating that the property holds everywhere.
Lemma 4.1. For all #.react .
Proof. The claim holds initially because
#. The only line that assigns a nonzero value to x is 15,
which preserves the claim because by definition, #.act #
#.react for all #.
Lemma 4.2. For all #.y equals 0 or #.react or #.x.
Proof. The claim holds initially because root.y = root.x
and . The only lines that modify x
are 4, 12, and 15. The only lines that modify y are 3, 4, 12,
and 15. By inspection of the code, all of these lines trivially
preserve the claim.
Lemma 4.3. Let P denote the predicate that every node
in #.anc has a positive x value and every node that is neither
in #.anc nor a child of a node in #.anc has a zero x value.
Then P holds initially and it is a loop invariant of the up
loop, the down loop, and the main loop.
Proof. Initially, P holds because
and
Let A denote #.anc and let B denote the set of nodes that
are neither in A nor children of the nodes in A.
Every iteration of the up loop moves # to its parent. To
avoid confusion, we use # to denote the old node (i.e., child)
and # to denote the new node (i.e., parent). An iteration
of the up loop removes # from A, adds #.ch to B, and sets
the x value of #.ch to 0. Therefore, it preserves P .
Every iteration of the down loop moves # to one of its chil-
dren. To avoid confusion, we use # to denote the old node
(i.e., parent) and # to denote the new node (i.e., child).
Suppose the down loop takes the first branch of the outer if
statement. Then it adds # , which has a positive x value, to
A and removes # .ch from B. Hence it preserves P . Suppose
the down loop takes the second branch of the outer if state-
ment. If line 12 is executed, P is preserved because line 12
preserves both A and B and only changes the x value of the
nodes in neither A nor B. Then lines 14 and 15 preserves P
because they add # , which has a positive x value after line
15, to A and removes # .ch from B. Hence, it preserves P .
The main loop preserves P because both the up loop and
the down loop preserve P .
Lemma 4.4. For all #.y #.x.
Proof. The claim holds initially because
all #. The only lines that modify the x or y field are 3, 4,
12, and 15. At lines 4, 12, and 15, the x and y fields become
the same value. It follows from Lemma 4.3 and the guard of
the up loop that just before line 3, #= root and #.x > 0. It
then follows from Lemmas 4.1 and 4.2 that line 3 preserves
#.y #.x.
We now introduce the notion of an active sequence to
our subsequent proofs. A sequence #a0 , a1 , . , ar #,
called i-active if a
all
Lemma 4.5. For every internal node #, the nonzero x
fields of the children of # form an i-active sequence, where
Proof. The claim holds initially because
root . The only lines that modify the x field are 4, 12,
and 15. Lines 4 and 12 preserve the claim because the x
fields of the children of # all become preserves
the claim (for #.parent ) because #.x becomes #.act , which
by definition equals g(i +1, k - j), where
and j equals the number of children of #.parent that have a
positive x field.
Lemma 4.6. Let P (#) denote the predicate that for all #
that are not ancestors of #.y #.react . Then P (#) holds
initially and P (#) is a loop invariant of the up loop, the
down loop, and the main loop.
Proof. The predicate P (#) holds initially because
root and . The up loop preserves
(#) because every iteration first establishes #.y = #.react
and then moves # to its parent. The down loop preserves
it does not set the y field to a nonzero value.
The main loop preserves P (#) because both the up loop and
the down loop preserve P (#).
4.2 Colorings
In order to facilitate the presentation of an o#ine algorithm
in Section 4.3, we introduce the notion of colorings in
this section and the notion of consistent placements in the
next.
A coloring of T (recall that T is the tree of caches) is an
assignment of one of the colors {white, black} to every node
in T so that the following rules are observed: (1) root is
white, (2) every internal white node has exactly one black
child and k-1 white children, and (3) the children of a black
node are black. A coloring is called consistent (with ADV)
if for every #, if #.x > 0, then # is white.
For any coloring C and any pair of sibling nodes # and
#, we define swapc(C, #) (swap coloring) as the coloring
obtained from C by exchanging the color of each node in the
subtree rooted at # with that of the corresponding node in
the subtree rooted at #. (Note that the subtrees rooted at
# and # have identical structure.)
4.3 Consistent Placements
A placement is colorable if there exists a coloring C such
that: (1) for each white internal node # of T , the set of files
#.files are stored in (and fill) the caches associated with the
unique black child of #; (2) for each white leaf # of T , the
set of files #.files is stored in (and fill) the cache
#. Note that in the preceding definition of a colorable place-
ment, the coloring C, if it exists, is unique. A placement is
called consistent if it is colorable and the associated coloring
is consistent.
For any placement P and any pair of siblings # and #, we
define swapp(P, #) (swap placement) as the placement obtained
from P by exchanging the contents of each cache in #
with that of the corresponding cache in #. Note that for any
colorable placement P with associated coloring C and any
pair of sibling nodes # and #, the placement swapp(P, #)
is colorable, and its associated coloring is swapc(C, #).
4.4 The Offline Algorithm OFF
For every internal node #, we maintain an additional variable
#.last defined as follows. First, we partition the execution
of the adversary algorithm into epochs with respect to
#. The first epoch begins at the start of execution. Each
subsequent epoch begins when either line 4 or line 12 is executed
with #. The variable #.last is updated at the
start of each epoch, when it is set to the child # of # for
which the line 15 is executed with # furthest in the
future. (If one or more children # of # are such that line
15 is never executed with # in the future, then #.last
is set to an arbitrary such child #.) Note that the variables
#.last are introduced solely for the purpose of analysis and
have no impact on the execution of ADV.
At any point in the execution of ADV, the values of the
last fields determine a unique coloring, denoted by COFF ,
as follows: root is white and the black child of each internal
white node # is #.last .
We define an o#ine algorithm OFF that maintains a
placement POFF as follows. We initialize POFF to an arbitrary
consistent placement with associated coloring COFF .
We update POFF to swapp(POFF , #) whenever line 4 or
line 12 is executed, where # and # denote the values of
#.last before and after the execution of the line. The algorithm
OFF uses the placement POFF to serve each request
generated in line 18. The placement POFF is not updated
when OFF serves a request; POFF is updated only at lines
4 and 12.
Lemma 4.7. Throughout the execution of ADV, POFF is
colorable and has associated coloring COFF .
Proof. Immediate from the way POFF is updated whenever
a last field is updated.
Lemma 4.8. Execution of line 4 or line 12 preserves the
consistency of COFF .
Proof. Assume that COFF is consistent before line 4. So
# is white in COFF before line 4, because by Lemma 4.3, #.x
is positive before line 4. By the definition of COFF , before
line 4, #.last is black. Let # be #.last before line 4, and let
# be #.last after line 4. Before and after line 4, the x values
of the descendants of # are equal to 0. By Lemma 4.3, the
x values of all proper descendants of # are equal to 0 before
and after line 4. Since line 4, the x values of
all descendants of # and # are equal to 0 after line 4. Hence,
the swapp operation preserves the consistency of COFF . The
same argument applies to line 12.
Lemma 4.9. Execution of line 15 preserves the consistency
of COFF .
Proof. Assume that COFF is consistent before line 15.
Line 14 implies that #= root just before line 15. Let #
denote #.parent . By Lemma 4.3, # .x > 0 and hence # is
white before line 15. Therefore, by Lemma 4.7, # .last is the
black child of # .
Let t denote the start of the current epoch for # , i.e., t
is the most recent time at which # .last was assigned. Just
after time t, the x values of all children of # were equal
to 0. By the definition of t, no child of # has been set to
0 since time t. By Lemma 3.1, every internal node has at
least one child with x equal to 0. Therefore, from time t
until after the execution of line 15, at most k - 1 children
of # have had their x value set to a nonzero value. (Note
that line 15 is the only line that sets x to a nonzero value.)
Thus, by the definition of last , # .last.x remains 0 after the
execution of this line. Thus, # .last #. Since # is white
and # .last is black in COFF , we conclude that # is white in
COFF . So COFF remains consistent even with the additional
constraint that # is required to be white. (Note that #.x is
set to a positive value by line 15.)
Lemma 4.10. The placement POFF is always consistent.
Proof. We observe that COFF is always consistent, due
to Lemmas 4.8 and 4.9, and the observation that lines 4,
12, and 15 are the only lines that can a#ect the consistency
of COFF (because they are the only lines that modify the
last field or the x field of any node). It then follows from
Lemma 4.7 that POFF is always consistent.
4.5 A Potential Function Argument
Let ON denote an arbitrary online b-feasible algorithm. In
this section, we use a potential function argument to show
that ON
#,
and #
. Let TON denote the total cost incurred by
ON. Similarly, we let TOFF denote the total cost incurred
by OFF, except that we exclude from TOFF the cost of initializing
POFF . (This initialization cost is taken into account
in the proof of Theorem 1 below.) We define #, a potential
as:
#.anc#=root
#.parent .diam - #.x
#.parent .diam - (#.x - #.y
For convenience of exposition, we account for the cost of
moving from the empty placement to the first placement
separately.
Lemma 4.11. The cost incurred by swapp(P, #) is at
most
#.parent .diam, where
Proof. The cost incurred is the cost of exchanging the
files placed in # and # with each other, which is at most
#.parent .diam. Note
that # and # have the same capacity.
Lemma 4.12. The predicate # 0 is a loop invariant of
the up loop.
Proof. Every iteration of the up loop moves # to its
parent. To avoid confusion, we use # to refer to the old
node (i.e., child) and we use # to refer to the new node
(i.e., parent). Consider the change in # in a single iteration
of the up loop. ON incurs no cost in the up loop. By the
definition of #, line 3 preserves #. By Lemma 4.4, line 4
does not increase #. Let
after the execution of line 4, OFF incurs a cost of at most
- #.diam to move from the current consistent
marking placement to the next. Thus, the total change in
# in an iteration is at most
(In the derivation above, the first inequality is due to the
guard of the up loop and line 3, and the second inequality is
due to the assumption that the diameters of the nodes are
# separated.)
Lemma 4.13. The predicate # 0 is a loop invariant of
the down loop.
Proof. Every iteration of the down loop moves # to one
of its children. To avoid confusion, we use # to refer to the
old node (i.e., parent) and # to refer to the new node (i.e.,
child). ON incurs no cost in the down loop. We consider
the following three cases.
Suppose that the outer if statement takes the first branch.
In this case, OFF does not incur any cost. Thus, the change
in # is
where the inequality is due to Lemma 4.6 and the guard of
the outer if statement.
Suppose that the outer if statement takes the second
branch and that line 12 is not executed. In this case, OFF
does not incur any cost. Thus, the change in # is
where the first inequality is due to Lemma 4.4 and the second
inequality is due to lines 14 and 15.
Suppose that the outer if statement takes the second
branch and that line 12 is executed. By Lemma 4.11, in
this case, OFF incurs a cost of
Thus, the change in #) due to line 12 is at most
#.ch
#.ch
(In the above derivation, the first inequality follows from
Lemma 4.6 and the first equality follows from Lemma 4.5.)
By the analysis of the previous case (i.e., the outer if statement
takes the second branch but line 12 is not executed),
lines 14 and 15 do not increase #. Thus, every iteration of
the down loop preserves # 0.
Lemma 4.14. Lines preserve # 0.
Proof. The guard of the down loop ensures that there
exists a file in #.missing just before line 18. Thus, ON incurs
a cost at least #.parent .diam #.diam at line 19. OFF
incurs a cost at most #.diam because it stores all the files
in #.missing # S i , in a child of #. Let u be the
cache where the request is generated, and let A be the set
of nodes on the path from # to u, excluding #. Since ON
adds a file in #.missing to u, the change in # is at most
#A
#.parent .diam
(In the above derivation, the last inequality follows from
8 .) At line 19, ON is allowed to make
arbitrarily many updates to its own placement. Suppose an
update causes the load of some nodes to increase. Then by
the definition of load , the set of nodes with an increased load
value form a path from, say #, to a leaf, and ON incurs a
cost of at least #.parent .diam. Let the set of nodes on this
path be B. Since the diameters of the nodes on this path
are # separated, the change of # is at most
#.parent .diam - #.parent .diam
#.parent .diam -
#.parent .diam
#.parent .diam
The claim of the lemma then follows.
Theorem 1. ON
-competitive.
Proof. Initially,
# 0 is a loop invariant of the main loop. Therefore, by
Lemmas 4.1 and 4.4, TON #
holds initially and is
a loop invariant of the main loop. Let c be the cost incurred
by OFF in moving from the empty placement to the first
placement. Note that TON serves every request with a cost at
least 1 (because the diameter of an internal node is at least
1). Hence, given an arbitrarily long sequence of requests,
TON grows unbounded. Therefore, we can make T ON
arbitrarily close to #
# by increasing the length N of the
request sequence generated by the program.
The# log d
bound on the competitive ratio for a capacity
claimed in the beginning
of Section 3, follows from d = 4bk and that OFF can choose
an arbitrarily large #.
5. DISCUSSION
Cooperative caching has in fact found its application in areas
other than distributed systems. For example, in NUCA
(NonUniform Cache Architecture), a switched network allows
data to migrate to di#erent cache regions according to
access frequency [8]. Although NUCA only supports a single
processor at the time of this writing, multiprocessor NUCA
is being developed, with data replication as a possibility.
6.



--R

Serverless network file systems.
Distributed paging for general networks.
On approximating arbitrary metrics by tree metrics.
Distributed paging.
The Harvest information discovery and access system.
Cooperative caching: Using remote client memory to improve file system performance.
A tight bound on approximating arbitrary metrics by tree metrics.
An adaptive
Placement algorithms for hierarchical cooperative caching.
Amortized e
Squid Internet object cache.



--TR
Amortized efficiency of list update and paging rules
The Harvest information discovery and access system
Serverless network file systems
Distributed paging for general networks
Placement algorithms for hierarchical cooperative caching
An adaptive, non-uniform cache structure for wire-delay dominated on-chip caches
Distributed Paging
A tight bound on approximating arbitrary metrics by tree metrics
Probabilistic approximation of metric spaces and its algorithmic applications
online computation;hierarchical cooperative caching