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. 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 a recently proposed 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.