CS369N: Beyond Worst-Case Analysis Lecture #2: Models of Data in Online Paging ∗
Tim Roughgarden · 2010
We first discuss some preliminaries from Sleator and Tarjan [16], a famous paper that founded the competitive analysis of online algorithms. The are many satisfying results in [16]; perhaps unfairly, we focus only on the less satisfying ones. 1 The setup is this: • There is a slow memory with N pages. • There is a fast memory (a cache) that can only hold k < N of the pages at a time. • Page requests arrive ”online”, one request per time step. • If the page request pt at time t is already in the cache, zero cost is incurred. • If pt is not in the cache, it needs to be brought in; if the cache is full, one of its k pages must be evicted (without knowing what the future requests will be). One unit of cost is incurred in this case. 2 In last lecture’s notation, we have thus defined cost(A, z) as the number of “page faults” (a.k.a. “cache misses”) that A incurs on the page request sequence z. We now come to a standard and important definition: the competitive ratio of algorithm A is its worst-case performance relative to an optimal offline algorithm OPT, which has full