On the Separation and Equivalence of Paging Strategies

  • Angelopoulos, S.
ORKG logo Add to ORKG
Publication date
January 2007

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

Extracted data

Related items

On the Separation and Equivalence of Paging Strategies
  • Angelopoulos, S.
January 2007

It has been experimentally observed that LRU and variants thereof are the preferred strategies for o...

On the separation and equivalence of paging strategies
  • Angelopoulos, Spyros
January 2007

It has been experimentally observed that LRU and variants thereof are the preferred strategies for ...

On the relative dominance of paging algorithms
  • Dorrigiv, Reza
  • López-Ortiz, Alejandro
  • Munro, J. Ian
September 2009

AbstractIn this paper, we give a finer separation of several known paging algorithms using a new tec...

We use cookies to provide a better user experience.