Caching data together with expiration times beyond which the data
are no longer valid is a standard method for promoting information
coherence in distributed systems, including the Internet, the
World Wide Web (WWW), and Peer-to-Peer (P2P) networks. We use the
framework of competitive analysis of online algorithms and study
upper and lower bounds for page eviction strategies in the case
where data have expiration times. We show that minimal adaptations
of marking algorithms achieve performance similar to that of the
well-studied case of caching without the expiration time
constraint. Marking algorithms include the widely-used Least
Recently Used (LRU) eviction policy. In practice, when data have
expiration times, the LRU eviction policy is used widely, often
without any consideration of expiration times. Our results explain
and justify this standard practice.