List update with probabilistic locality of reference

In this paper we study the performance of list update algorithms under arbitrary distributions that exhibit strict locality of reference and prove that Move-To-Front (MTF) is the best list update algorithm under any such distribution. We also show that the performance of MTF depends on the amount of locality of reference, while the performance of any static list update algorithm is independent of the amount of locality.

► We introduce a probabilistic model for list update with locality of reference.
► This model is based on the diffuse adversary model.
► We prove that MTF outperforms other algorithms in this model.