Competitive paging with locality of reference

Allan Borodin, Sandy Irani, Prabhakar Raghavan, Baruch Schieber

Research output: Contribution to journalArticlepeer-review

117 Scopus citations


The Sleator-Tarjan competitive analysis of paging (Comm. ACM 28 (1985), 202-208) gives us the ability to make strong theoretical statements about the performance of paging algorithms without making probabilistic assumptions on the input. Nevertheless practitioners voice reservations about the model, citing its inability to discern between LRU and FIFO (algorithms whose performances differ markedly in practice), and the fact that the theoretical competitiveness of LRU is much larger than observed in practice. In addition, we would like to address the following important question: given some knowledge of a program’s reference pattern, can we use it to improve paging performance on that program? We address these concerns by introducing an important practical element that underlies the philosophy behind paging: locality of reference. We devise a graph-theoretical model, the access graph, for studying locality of reference. We use it to prove results that address the practical concerns mentioned above. In addition, we use our model to address the following questions: How well is LRU likely to perform on a given program? Is there a universal paging algorithm that achieves (nearly) the best possible paging performance on every program? We do so without compromising the benefits of the Sleator-Tarjan model, while bringing it closer to practice.

Original languageEnglish (US)
Pages (from-to)244-258
Number of pages15
JournalJournal of Computer and System Sciences
Issue number2
StatePublished - Apr 1995
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science
  • Applied Mathematics
  • Computer Networks and Communications
  • Computational Theory and Mathematics


Dive into the research topics of 'Competitive paging with locality of reference'. Together they form a unique fingerprint.

Cite this