| Online Hierarchical Cooperative Caching ∗ Theory of Computing Systems (2008) | |||||||||||||||
Abstract | |||||||||||||||
| Abstract. 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 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 LRU that is constant-competitive when the capacity blowup is linear in d, the depth of the cache hierarchy. Furthermore, we exhibit an infinite family of depth-d hierarchies such that any randomized hierarchical cooperative caching algorithm with capacity blowup b has competitive ratio �(log(d/b)) against an oblivious adversary. Thus, our upper and lower bounds imply a tight bound of �(d) on the capacity blowup required to achieve constant competitiveness. ∗ Most of this work was done while X. Li was a Ph.D. student at UT Austin supported by NSF Grant | |||||||||||||||
Details der Publikation | |||||||||||||||
| |||||||||||||||