English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

On the Separation and Equivalence of Paging Strategies

MPS-Authors
/persons/resource/persons44020

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

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

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
Abstract
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.