Markov Paging (Extended Abstract)

This paper considers the problem of paging under the assumption that the sequence of pages accessed is generated by a Markov chain. The authors use this model to study the fault-rate of paging algorithms, a quantity of interest to practitioners. They first draw on the theory of Markov decision processes to characterize the paging algorithm that achieves optimal fault-rate on any Markov chain. They address the problem of efficiently devising a paging strategy with low fault-rate for a given Markov chain. They show that a number of intuitively good approaches fail. Their main result is an efficient procedure that, on any Markov chain, will give a paging algorithm with fault-rate at most a constant times optimal. Their techniques also show 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. >

Authors

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

Keywords

• Paging strategies
• Probability distribution
• Algorithm design and analysis
• Markov Chain
• Optimization Algorithm
• State Space
• Proof Of Theorem
• Types Of Problems
• Random Walk
• Linear Programming
• Linear Problem
• Cycle Length
• Previous Phase
• Markov Decision Process
• Triangle Inequality
• Memory Items
• Online Algorithm
• Defect Rate
• Adversary Model
• Probability Of System
• End Of Path
• Proof Sketch
• Distinct Vertices