Caching with expiration times

Parikshit Gopalan, Howard J. Karloff, Aranyak Mehta, Milena Mihail, Nisheeth K. VishnoiSODA 2002 · OpenReview

Abstract

Caching data together with expiration times beyond which the data is no longer valid is a standard method for promoting information consistency in distributed systems, including the Internet and WWW, large databases, and mobile telecommunications. We use the framework of competitive analysis of online algorithms and study page eviction strategies in the case where data has expiration times. We show that suitable adaptations of LRU and its generalizations, namely marking algorithms, are asymptotically optimal and, in the worst case, within a multiplicative factor 2 of the lower bounds. A key technical ingredient of our analysis is a covering invariant that captures some of the subtleties introduced by expiration times. The additional difficulty of dealing with expiration times is also reflected in our analysis of the randomized online marking algorithm, as well as the offline version of the problem for which we obtain a factor 3 approximation. We complement our theoretical findings with experiments on real and synthetic data.
BibTeX
@inproceedings{gopalan2002caching,
  author = {Parikshit Gopalan and Howard J. Karloff and Aranyak Mehta and Milena Mihail and Nisheeth K. Vishnoi},
  title = {{Caching with expiration times}},
  booktitle = {SODA},
  year = {2002},
  url = {https://openreview.net/forum?id=35QAlgJgQm},
}

Loading related content...

Figure