Online hierarchical cooperative caching

Abstract We address a hierarchical generalization of the well-known disk paging problem. In thehierarchical cooperative caching problem, a set of n machines residing in an ultrametric spacecooperate 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 the "least recently used"(LRU) paging algorithm 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? In this paper, we present a deterministic hierarchical generalization of LRUthat is constant-competitive when the capacity blowup is linear in d, the depth of the cachehierarchy. Furthermore, we exhibit an infinite family of depthd hierarchies such that any ran-domized hierarchical cooperative caching algorithm with capacity blowup b has competitiveratio \Omega (log db) against an oblivious adversary. Thus, our upper and lower bounds imply a tightbound of \Theta (d) on the capacity blowup required to achieve constant competitiveness