Motivation
A cache is useful because recently requested pages may be needed again. When a requested page is absent, however, the cache must make room before seeing the future requests. The decision is online: it must be made using the request sequence seen so far. An offline benchmark knows the entire sequence and can plan its evictions accordingly.
Competitive analysis compares the online algorithm's cost with the offline optimum on the same request sequence. This chapter gives a transparent phase proof of a bound for marking algorithms and a separate adversarial lower bound of for deterministic algorithms. The upper bound is deliberately elementary; it is not a claim that is the best possible guarantee for least-recently-used paging.
Definitions
Definition 7.3.1
(Paging model: hits, faults and cost)
There is a universe of pages and a cache of capacity . A request to a cached page is a hit and costs zero. A request to an uncached page is a fault and costs one: the requested page is loaded, and if the cache is full, one page is evicted. Both the online algorithm and offline optimum start with the same specified cache of distinct pages. We consider finite request sequences; an offline algorithm may use the future when deciding what to evict.
Definition 7.3.2
(Competitive ratio with an additive constant)
An algorithm is -competitive with additive constant if, for every finite sequence ,
where depends on and the fixed initial cache but not on . The additive term matters for short sequences; the ratio without it is undefined when the offline optimum costs zero.
Definition 7.3.3
(Phases of a request sequence)
Partition a nonempty request sequence into phases greedily. The first phase begins at the first request. Continue a phase while the next request is among its first distinct page names; a request to a new st distinct page starts the next phase. Each phase except possibly the last therefore contains exactly distinct pages.
Definition 7.3.4
(Marking algorithms)
A marking algorithm clears all marks at the beginning of each phase and marks each requested page. On a fault it evicts an unmarked page. Such a page is always available: before serving a new distinct page within a phase, fewer than different pages have been marked, and the cache holds pages. Least recently used (LRU) is a marking algorithm, because every marked page was used during the present phase and every unmarked cached page was last used earlier.
Theorems
Theorem 7.3.5
(A simple marking bound)
For any request sequence partitioned into phases, a marking algorithm incurs at most faults and the offline optimum incurs at least faults. Thus every marking algorithm is -competitive with additive constant .
Theorem 7.3.6
(Deterministic lower bound)
For every deterministic online paging algorithm with a cache of size , and every , there is no constant such that its cost is at most on every sequence. This remains true on a universe of only pages, provided the initial cache lies in that universe.
Proofs
Proof: marking phases
Proof
(Phase counting for marking algorithms)
In one phase, a marking algorithm never evicts a page after that page has been requested and marked. Consequently each distinct page can fault at most once in that phase, and at most faults occur. Summing over phases gives the online upper bound.
For each boundary between consecutive phases, the first request of the later phase is a page not requested in the preceding phase. Since the preceding phase contains distinct pages, the union of those two phases contains at least distinct pages. If the offline optimum had no fault anywhere in that two-phase interval, its cache would remain unchanged throughout the interval and would contain all those pages, impossible with capacity . Hence each adjacent pair of phases contains at least one offline fault.
A fault belongs to a single phase and therefore lies in at most two adjacent-phase pairs. Counting the pairs gives . Combining the bounds yields
The pairing argument counts each fault at most twice, not exactly twice. It is intentionally conservative and establishes the stated factor without claiming a tight upper bound.
Proof X-ray
Where the factor two enters
The marking rule and the cache capacity each do separate work. On the online side the marking rule alone gives at most one fault per distinct page per phase, hence at most per phase; no property of the offline schedule is used. On the offline side the key move is the certificate: the pages of phase together with the first request of phase are distinct names, and a cache of pages that never changes cannot hold them, so some fault occurs in the pair. The pairs overlap, since phase belongs to both and , so one offline fault in an interior phase can serve two pairs. Hence the number of pairs is at most twice the number of offline faults. Treating the witnessing faults as automatically distinct would give , an unjustified stronger claim that would turn the factor into .
Proof: an adversary against any deterministic algorithm
Proof
(An adaptive adversary against a deterministic algorithm)
Fix a deterministic online algorithm and a universe of exactly pages containing its initial cache. Repeatedly request a page of that is not in the algorithm's current cache. There is always at least one such page. The algorithm faults at every request. Since the algorithm is deterministic, this adaptive procedure defines a particular finite sequence once its length is fixed; the resulting sequence can be used as a fixed worst-case input for that algorithm.
To bound the offline optimum on this sequence, partition it into the same phases. Every complete phase has distinct requests and hence at least requests. Therefore the number of phases satisfies .
If , there are at most distinct requests, so the offline optimum is at most by retaining each page once requested. Suppose now that . Then the first phase has distinct pages. An offline strategy that knows the phases serves it with at most faults: it retains each page requested in that phase and, on a fault, evicts a page outside the first phase's set. There is always such a page if space is needed. At the end its cache contains precisely the phase's distinct pages.
Any two -element subsets of the -element universe differ in at most one page. At the next complete phase, the offline strategy keeps their common pages and, if the one new page is requested, evicts the one page outside the new phase set. Thus it incurs at most one fault in that phase and ends with its entire set in cache. For a final incomplete phase, extend its requested set arbitrarily to a -element subset of and use the same argument. Therefore
The online cost is exactly . If a fixed inequality held for some , then for every . The coefficient of on the right is strictly below one, so sufficiently large contradicts the inequality. This proves the lower bound, including the additive-constant convention.
Worked examples
Worked example 7.3.7
(A two-page LRU trace)
Take cache , capacity two, and requests . LRU hits on , faults on and evicts , faults on and evicts , then faults on and evicts . Its cost is three. The phases are and , each with two distinct pages. Their union has three distinct pages, so any offline schedule must fault at least once across the two phases.
Worked example 7.3.8
(A short offline comparison)
For the same cache and requests, an offline strategy hits , then loads while evicting because the next request is . It hits , then loads , for two faults. One fault cannot suffice: at the request the cache must evict or , and the evicted page is requested later with no intervening way to load it at zero cost. Thus the offline optimum is exactly two.
Worked example 7.3.9
(A deterministic adversary for capacity one)
With universe and initial cache , request , then request whichever of is absent. Capacity one forces the alternating sequence , and every request faults for both the online and offline algorithms. The lower bound is , consistent with this special case.
Worked example 7.3.10
(Two phase sets overlap heavily)
With and universe , consecutive complete phase sets might be and . An offline cache holding the first set needs only to replace by when is first requested in the second phase. The internal order of requests can be arbitrary; the offline strategy retains all three pages once they are loaded for that phase.
Common mistakes
Counterexample mode
A rule that evicts marked pages
Claim: every deterministic demand-paging rule satisfies the guarantee. This is false without the marking property. Take , initial cache (loaded in that order), and the rule that always evicts the most recently loaded page. On the requests of length it faults every time: loading evicts , loading evicts , and so on, so the cost is . An offline schedule evicts at the first request, keeps and , and pays in total. The bound fails at , and no constant can repair it. The rule is not a marking algorithm: once and have both been requested in the first phase, it evicts the marked page . The remedy is the hypothesis of the theorem: evict only unmarked pages.
Common mistake
(Extending the adversary argument to randomized algorithms)
For a deterministic algorithm and a fixed length, simulating the construction determines a single request sequence in advance, so it can serve as a fixed worst-case input. This does not automatically extend to a randomized algorithm against an oblivious adversary: the page missing from the cache can depend on private random choices, so the quantifiers and the expectation must be specified separately.
Common mistake
(Treating the gap between the bounds as the exact ratio)
The upper bound and the lower bound do not match. They show a valid guarantee and a universal obstruction, not the exact competitive ratio of a particular online rule. A sharper analysis may close the gap, but it is not proved here.
Why phases are useful
A phase records the working set of recent requests rather than a fixed number of time steps. It may be very long if the same few pages recur, but a marking algorithm pays for any one of them at most once within that phase. This makes the upper bound insensitive to repeated hits.
The offline comparison is harder because the optimum may enter a phase with pages chosen using future knowledge. It need not fault in every individual phase. Looking at two consecutive phases supplies a certificate: their combined requests exceed the cache capacity. The price of this simple certificate is that one offline fault can support two neighboring certificates.
The lower bound uses a different fact. On a universe of pages, two complete phase sets overlap in at least pages. Knowledge of the next set lets an offline strategy prepare with at most one change per phase. Meanwhile the online algorithm is forced to fault on every request. Both the overlap and the offline knowledge are essential to the argument.
Summary
Marking limits an online algorithm to one fault per distinct page per phase. Consecutive phases require an offline fault between them, giving a competitive guarantee with an additive . A deterministic adversary on pages forces an asymptotic lower bound of against every deterministic online algorithm.
Exercises
Quick check
(For , partition into phases and give the number of distinct pages in each.)
Solution · Answer
The phases are , , and . Their distinct-page counts are two, two and one. The request starts the second phase because it would be a third distinct page in the first; similarly starts the third.
Quick check
(In the same sequence, why can a marking algorithm fault at most twice in each phase even if a phase contains many requests?)
Solution · Answer
After its first request in the phase, a page is marked and cannot be evicted during that phase. Each phase contains at most two distinct pages, so there can be at most one fault per page and at most two faults total.
Quick check
(With and , an offline cache holds and the next complete phase uses . Describe a strategy with at most one fault.)
Solution · Answer
Keep . If is requested, fault once, load and evict . All pages requested in that phase are then cached, so later requests hit. If is not requested, the phase set was not actually complete as stated.
Quick check
(The deterministic adversary produces a length- sequence for . State an upper bound for the offline cost from the proof and explain why the online cost is .)
Solution · Answer
The proof gives . At each request the adversary selects a page missing from the online cache, so the online algorithm faults on every one of the requests. The offline bound need not be an integer; it is an upper bound on an integer cost.