User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse




Conference Paper

On the Separation and Equivalence of Paging Strategies


Angelopoulos,  Spyros
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Ressource
No external resources are shared
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available

Angelopoulos, S. (2007). On the Separation and Equivalence of Paging Strategies. In N. Bansal, K. Pruhs, & C. Stein (Eds.), Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 229-237). Philadelphia, PA: SIAM.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-2027-9
It has been experimentally observed that LRU and variants thereof are the preferred strategies for on-line paging. However, under most proposed performance measures for on-line algorithms the performance of LRU is the same as that of many other strategies which are inferior in practice. In this paper we first show that any performance measure which does not include a partition or implied distribution of the input sequences of a given length is unlikely to distinguish between any two lazy paging algorithms as their performance is identical in a very strong sense. This provides a theoretical justification for the use of a more refined measure. Building upon the ideas of concave analysis by Albers et al. [AFG05], we prove strict separation between LRU and all other paging strategies. That is, we show that LRU is the unique optimum strategy for paging under a deterministic model. This provides full theoretical backing to the empirical observation that LRU is preferable in practice.