Competitive Paging as Cache Size Varies

Abstract:

Recent efforts to analyze paging strategies have examined the competiveness of various strategies - the worst-case ratio of the number of page faults made by a strategy on a sequence to the minimum number possible for any strategy with the same cache size. Two generalizations of competitive analysis have been
considered: comparing strategies using different size caches and allowing randomized strategies. In this report, we study how well a randomized strategy can compare against a strategy with a smaller cache, and we study how competitiveness is related to the rate at which page fault rate decreases as the cache size increases. First, we show that the marking algorithm of Fiat et al. using a cache of size k has an expected number of faults within a factor of about ln h/(k-h+1) times the minimal number using a smaller cache of size h, and that this factor, called the (h,k)-competitiveness of the strategy, is within a factor of about two of optimal. Second, we show that for any fixed sequence, to the extent that the fault rate decreases only polynomially as the cache size increases, the optimal deterministic (k, k)-competitiveness
is reduced to O(ln k) for most choices of k, and the optimal randomized competitiveness is reduced to 2 ln ln k + O(1) for most k.