✍ Scribed by Neal E. Young
No coin nor oath required. For personal study only.
In evaluating an algorithm, worst-case analysis can be overly pessimistic. Average-case analysis can be overly optimistic. An intermediate approach shows that an algorithm does well on a broad class of input distributions. E. Koutsoupias and C. Ž H. Papadimitriou 1994, in ''Proc. of the 35th IEEE Annual Symp. on Foundation . of Computer Science,'' pp. 394᎐400, IEEE Press, New York recently analyzed the Ž . least-recently-used LRU paging strategy in this manner, analyzing its performance on an input sequence generated by a so-called diffuse adversaryᎏone that must choose each request probabilistically so that no page is chosen with probability more than some fixed ⑀ ) 0. They showed that LRU achieves the optimal Ž . competitive ratio for deterministic on-line algorithms , but they did not determine the actual ratio. In this paper we estimate the optimal ratios within roughly a factor of two for both deterministic strategies and randomized strategies. Around the Ž . Ž . threshold ⑀ f 1rk where k is the cache size , the optimal ratios are both ⌰ ln k .
Ž . Below the threshold the ratios tend rapidly to O 1 . Above the threshold the ratio Ž . is unchanged for randomized strategies but tends rapidly to ⌰ k for deterministic Ž . ones. We also show that the competitive ratios for First-in-first-out FIFO and Ž . Flush-when-full FWF are both k when ⑀ G 1rk. In contrast, the ratio for LRU is less than 2 ln k q 4 when ⑀ s 1rk. It is folklore that LRU outperforms FIFO in practice, but to date the only other variant of competitive analysis in which LRU has been shown to outperform FIFO is the access graph model. For completeness, we give an alternate proof of the optimality of LRU.
📜 SIMILAR VOLUMES