Seminario Interdipartimentale di Algoritmica
 
 

DIS - Dipartimento di Informatica e Sistemistica, via Salaria 113
C3 Room, second floor

Abstract:
In this paper we explore the effects of locality on the performance of paging algorithms. Traditional competitive analysis fails to explain important properties of paging assessed by practical experience. In particular, the competitive ratios of paging algorithms that are known to be efficient in practice (e.g. LRU) are as poor as those of naive heuristics (e.g. FWF). It has been recognized that the main reason for these discrepancies lies in an unsatisfactory modelling of locality of reference exhibited by real request sequences. With paging as one of the motivating applications, many extensions to competitive analysis have been proposed in the recent past. Among the most interesting ones, the diffuse adversary proposed by Koutsoupias and Papadimitriou forces the adversary to generate request sequences according to properly defined families of probability distributions. The speficic adversary they propose, however, does not explicitly model locality of reference. We explicitely address this issue, proposing an adversarial model in which the probability of requesting a page is also a function of the page's age. In this way, our approach allows to capture the effect of locality of reference. We consider several families of distributions and we prove that the competitive ratio of LRU becomes constant as locality increases, as expected. This result is strengthened when the distribution satisfies a further concavity/convexity property: in this case, the competitive ratio of LRU is always constant. We also propose a family of distributions parametrized by locality of reference and we prove that the performance of FWF rapidly degrades as locality increases, while the converse happens for LRU.