Online paging and file caching with expiration times

We consider a paging problem in which each page is assigned an expiration time at the time it is brought into the cache. The expiration time indicates the latest time that the fetched copy of the page may be used. Requests that occur later than the expiration time must be satisfied by bringing a new copy of the page into the cache. The problem has applications in caching of documents on the World Wide Web (WWW). We show that a natural extension of the well-studied least recently used (LRU) paging algorithm is strongly competitive for the uniform retrieval cost, uniform size case. We then describe a similar extension of the recently proposed Landlord algorithm for the case of arbitrary retrieval costs and sizes, and prove that it is strongly competitive. The results extend to the loose model of competitiveness as well. © 2001 Elsevier Science B.V. All rights reserved.