article · 2000

MARKOV PAGING

Anna R. Karlin, Steven J. Phillips, Prabhakar Raghavan

Cited by 0Abstract and details only

Abstract

This paper considers the problemof paging under the assumption that the sequence of pages accessed is generated by a Markov chain. We use this model to study the fault-rate of paging algorithms. We first draw on the theory of Markov decision processes to characterize the paging algorithmthat achieves optimal fault-rate on any Markov chain. Next, we address the problemof devising a paging strategy with low fault-rate for a given Markov chain. We show that a number of intuitive approaches fail. Our main result is a polynomial-time procedure that, on any Markov chain, will give a paging algorithm with fault-rate at most a constant times optimal. Our techniques show also that some algorithms that do poorly in practice fail in the Markov setting, despite known (good) performance guarantees when the requests are generated independently from a probability distribution.

Cite this paper

APA 7

Karlin, A. R., Phillips, S. J., & Raghavan, P. (2000). MARKOV PAGING.

MLA 9

Karlin, Anna R., et al. “MARKOV PAGING.” 2000.

Chicago

Karlin, Anna R., Steven J. Phillips, and Prabhakar Raghavan. 2000. “MARKOV PAGING.”

Harvard

Karlin, A.R., Phillips, S.J. and Raghavan, P. (2000) ‘MARKOV PAGING’.

BibTeX

@article{karlin2000markov,
  title = {{MARKOV PAGING}},
  author = {Karlin, Anna R. and Phillips, Steven J. and Raghavan, Prabhakar},
  year = {2000}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.