CS264: Beyond Worst-Case Analysis Lecture #4: Parameterized Analysis of Online Paging∗

Recall our three goals for the mathematical analysis of algorithms — the Explanation Goal, the Comparison Goal, and the Design Goal. Recall that, for the online paging problem, traditional competitive analysis earns a pretty bad report card on the first two goals. First, the competitive ratios of all online paging algorithms are way too big to be taken seriously as predictions or explanations of empirical performance. Second, while competitive analysis does identify the least recently used (LRU) policy as an optimal online algorithm, it also identifies less laudable policies (like first-in first-out (FIFO) or even flush-when-full (FWF)) as optimal. Last lecture introduced resource augmentation guarantees. This approach made no com-promises about worst-case analysis, but rather changed the benchmark — restricting the offline optimal algorithm to a smaller cache, which of course can only make competitive ratios smaller. The primary benefit of resource augmentation is much more meaningful and interpretable performance guarantees, which is good progress on the Explanation Goal. A key drawback is that it failed to differentiate between the LRU policy and the FIFO and FWF policies. Intuitively, because the empirical superiority of LRU appears to be driven by the properties of “real-world ” data, namely locality of reference, we can’t expect to sep-arate LRU from other natural paging algorithms (like FIFO) without at least implicitly articulating such properties. The goal of this lecture is to parameterize page sequences according to a natural measure of locality, to prove parameterized upper and lower bounds on the performance of natural paging policies, and (finally!) to prove a sense in which LRU is strictly superior to FIFO (and FWF). As a bonus to this progress on the Comparison Goal, we’ll obtain good absolute performance guarantees that represent a step forward for the Explanation Goal. ∗ c©2014, Tim Roughgarden