Motivated by the fact that competitive analysis yields too pessimistic results when applied to the paging problem, there has been considerable research interest in refining competitive analysis and in developing alternative models for studying online paging. The goal is to devise models in which theoretical results capture phenomena observed in practice.

In the talk a new, simple model for studying paging with locality of reference is presented. The model is closely related to Denning's working set concept and directly reflects the amount of locality that request sequences exhibit.

We use the page fault rate to evaluate the quality of paging algorithms, which is the performance measure used in practice. In our model LRU is optimal whereas FIFO and deterministic marking strategies are not optimal in general.

This is joint work with Susanne Albers and Oliver Giel.

Host: Joan Boyar