ALCOMFT-TR-03-72

Luca Becchetti
Modeling Temporal Locality in Paging: A tighter Analysis of LRU and FWF
Rome. Work package 4. November 2003.

Abstract: In this paper, we extend the diffuse adversary approach for paging initially proposed in [KP94], with the aim of modelling locality of reference. We consider two very general families of distributions, parametrized by their expected values and standard deviations.

We prove that LRU's competitive ratio rapidly becomes constant as the standard deviation becomes small, a result that is further improved when the distribution satisfies a concavity property.

In contrast, we prove that FWF performs poorly with respect to the distributions e propose. We think this result provides one theoretical explanation of a phenomenon that is very well known in practice, but that was so far not completely assessed by theory.

Postscript file: ALCOMFT-TR-03-72.ps.gz (102 kb).