Computer Science Colloquium, 2006-2007

Alex Lopez-Ortiz
March 14, 2007

On the Separation and Equivalence of Paging Strategies: LRU is the sole optimum


On-line paging algorithms are analyzed using competitive analysis, in which the performance of on-line algorithm on a sequence is normalized by the performance of the optimal on-line algorithm on that sequence. This measure can lead to algorithms that focus on the worst case at the expense of the every-day case as well as to lack of separation between algorithms whose performance vary wildly in practice, in particular Least-Recently Used and Flush-When-Full have the same competitive ratio. A long standing open problem in the field is to develop a natural model for online paging, with no pre-ordained knowledge of the request sequence which could separate all known algorithms. In this talk we introduce a new model developed from first principles which separates between LRU and all other paging strategies. The results extend to other online settings such as list update and robot motion planing.

This is joint work with Reza Dorrigiv and Spyros Angelopoulos.

Benny Pinkas