Markov paging

This paper considers the problem of paging under the assumption that the se quence of pages accessed is generated by a Markov chain. We use this model to study the fault-rate of paging algorithms. We rst draw on the theory of Markov decision processes to characterize the paging algorithm that achieve s optimal fault-rate on any Markov chain. Next, we address the problem of d evising 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 polyn omial-time procedure that, on any Markov chain, will give a paging algorith m with fault-rate at most a constant times optimal. Our techniques show als o that some algorithms that do poorly in practice fail in the Markov settin g, despite known (good) performance guarantees when the requests are genera ted independently from a probability distribution.