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 widelyused 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 o#ine 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#13 log n) lower bound on the competitive ratio of any online hierarchical cooperative caching algorithm with capacity blowup O((log n) ), where # denotes an arbitrarily small positive constant