Motivation
A phase argument gives a simple competitive bound for marking algorithms. It counts an offline fault in at most two neighboring phase pairs, so it deliberately leaves a gap. Least recently used paging (LRU) has a sharper guarantee: with the same initial cache, it suffers at most faults for each offline fault.
The proof compares the two caches after every request. Merely counting their different pages is not enough to explain how a hit changes LRU's recency order. A weighted potential records both which online pages are missing from the offline cache and how recently each was used. The weights are chosen so that an LRU fault pays for itself by decreasing potential.
Definitions
Definition 7.4.1
(Demand paging against an offline schedule)
There is a finite or infinite page universe, and both caches have capacity . Both begin with the same pages; LRU is given a fixed initial recency ordering. A hit costs zero. On a fault, the requested page is loaded, one cached page is evicted and the cost is one. The offline schedule knows the whole finite request sequence but, like LRU, changes its cache only to serve a fault. This demand-paging model includes an offline optimum for this problem.
Definition 7.4.2
(LRU cache and recency rank)
Write for the LRU cache and for the offline cache. Rank the pages of from for most recently used to for least recently used. A request moves its page to rank one, shifting intervening pages one rank farther from the front. On a miss, LRU evicts the page of rank and inserts the requested page at rank one.
Definition 7.4.3
(Recency-weighted potential)
Define the nonnegative potential
The most recent online page has weight and the least recent has weight one. A page contributes only if it is in LRU's cache but not the offline cache. Identical initial caches have potential zero.
Theorems
Theorem 7.4.4
(LRU is k-competitive)
For every finite request sequence and every offline demand-paging schedule with the same initial cache, LRU incurs at most times as many faults as that schedule. In particular, .
Theorem 7.4.5
(Sharpness among deterministic algorithms)
No deterministic online paging algorithm can have competitive factor strictly below , even allowing an additive constant independent of the request sequence. Consequently the factor in the LRU theorem is optimal for deterministic algorithms in this model.
Proofs
Proof: charge the offline step first
Proof
(Charge the offline step, then the LRU step)
Process each request in two conceptual steps. First let the offline schedule serve the request, keeping LRU's cache and ranks fixed. Then let LRU serve it, keeping the updated offline cache fixed. This is only an accounting order; the two schedules remain independent and see the same request.
If the offline step is a hit, neither cache nor potential changes. If it is a fault, the requested page enters and at most one page leaves . Adding a page to can only remove a term from the potential. Removing a page from can add at most one term, whose weight is at most . Thus an offline fault increases by at most . Immediately after this step the requested page belongs to .
Now consider the LRU step. If the request is a hit in , its page is in and contributes no term. Moving it to rank one shifts some other pages one rank farther back. Their weights decrease by one, and all other weights stay fixed. The potential cannot increase; LRU pays zero.
If LRU faults, the requested page is in but not in . LRU evicts its rank- page , then inserts the requested page at rank one. If , the removed term has weight one. If , the equal cache sizes and the requested page in imply that some page lies in . That page is not and shifts one rank farther back, decreasing its weight by one. In either case the new requested page contributes zero, no other term increases, and decreases by at least one. The decrease pays for LRU's one fault.
Let be the two fault indicators for request , and let be the total change over both conceptual steps. The preceding cases give
Summing over the sequence telescopes the potential changes. The initial potential is zero, and the final potential is nonnegative. Therefore total LRU faults are at most times total offline faults. Since the offline schedule was arbitrary, choose an optimum to obtain the theorem.
Proof X-ray
Why the LRU miss decreases potential
If the evicted page is missing offline, its weight-one term disappears. Otherwise the requested page is an offline-only page, so equal cache sizes force some different online-only page; that page becomes one position less recent and loses one unit of weight.
Proof: the deterministic lower bound
Proof
(Missing-page adversary and phases)
The companion paging chapter constructs, for any deterministic online algorithm, a sequence over pages by repeatedly requesting a page missing from its current cache. The online algorithm faults on all requests. Partitioning that fixed resulting sequence into phases of at most distinct pages gives an offline schedule with cost at most : after the first phase, consecutive phase page sets differ in at most one page.
Thus for any and fixed additive constant , the inequality fails for sufficiently large . The construction is deterministic once the algorithm and are fixed. It proves that no deterministic algorithm has a smaller competitive factor, while the potential proof establishes that LRU attains .
Worked examples
Worked example 7.4.6
(Two requests with one offline fault)
Let and initially both caches contain , with most recent for LRU. Request . Suppose offline evicts , while LRU evicts . Both fault. The new caches are and , with LRU order . Only contributes, at rank two, so . Request next. Offline hits; LRU faults and evicts , reducing the potential to zero. LRU has two faults to the offline schedule's one, meeting the factor-two bound.
Worked example 7.4.7
(An offline fault can increase the potential)
With , suppose the caches initially agree and the LRU order is . The request is . If offline evicts first, the unchanged LRU cache contains but offline does not, so the potential rises from zero to three. The subsequent LRU fault evicts and inserts , reducing this potential to two. The offline increase is at most , exactly as the proof permits.
Worked example 7.4.8
(An LRU hit need not change the potential)
Let , , and LRU order . A request to is a hit for both schedules. LRU changes its order to , but stays empty and the potential remains zero. Recency can change even when no fault occurs.
Worked example 7.4.9
(The evicted page can belong to the offline cache)
Let , with LRU order and offline cache . The potential is two because is online-only at rank one. Request : offline hits and LRU evicts , which is in the offline cache. The online-only page shifts to rank two, lowering its weight from two to one. This pays for the LRU fault even though the evicted page itself contributed no potential.
Common mistakes
Counterexample mode
Cardinality alone can stay constant on an LRU fault
In the preceding example, before the request , and afterward it is still . Its cardinality stays one. The recency-weighted potential nevertheless falls from two to one. Thus counting cache differences alone does not justify the one-unit decrease used in this proof.
Common mistake
(The accounting order is not an information advantage)
The comparison is with a fixed offline schedule on the same request sequence. The conceptual order of the two updates does not mean that LRU can see the offline cache or its eviction. It is an analytical device used after both decisions are specified.
Common mistake
(Reading the factor k as a prediction)
The factor is a worst-case guarantee over sequences. It does not predict that LRU always has times the optimum cost, and it does not settle the competitive behavior of randomized algorithms. An adaptive adversary that observes random cache contents requires a separately stated model.
Why recency weights are arranged this way
A recent online-only page is likely to survive many future LRU evictions. Giving it a larger weight supplies a reserve that can be spent as it becomes less recent. Each request to a different page moves it back at most one position and decreases its contribution by one. At the bottom of the order its weight is exactly one, so evicting it removes the last unit.
By contrast, when the requested page is already in the offline cache, moving it to the front cannot add a contribution of its own. This is why the proof updates offline first. An offline fault can increase the reserve, but only by exposing one online page that the offline schedule evicts; that page's weight is at most . The cost comparison follows by balancing these local changes over the entire sequence.
The initial-order convention affects which page LRU evicts on an early tie, but the inequality holds for every fixed initial order. Starting both caches with the same page set gives potential zero. With different initial caches, the same calculation gives an additive initial-potential term, at most ; the strict inequality without that term is not asserted for unrelated initial states.
Reading the amortized inequality
The potential is an accounting quantity, not money paid by either cache. A single request can make the expression negative: an LRU hit may push several online-only pages back in the order at once. Negative amortized cost is harmless because the potential cannot fall below zero over the whole execution. It represents previously accumulated reserve being released.
The offline schedule in the proof need not itself be optimal. For example, if a particular schedule has ten faults and LRU has at most , the inequality is true but may be weak. Selecting a minimum-cost offline schedule after proving the inequality for every schedule yields the comparison with . This order of reasoning avoids assuming anything about which page an optimum evicts.
An implementation needs to maintain membership and recency order, for example with a dictionary and a doubly linked list. Its actual running time depends on the dictionary's operations and computational model. The theorem counts page faults; it does not count the CPU work of maintaining the list or claim any particular dictionary bound.
Against an oblivious adversary, randomized marking has a factor of only logarithmic order.
A natural next question
Can randomness beat the factor k?
Against an oblivious adversary, randomized marking has a factor of only logarithmic order.
The lower bound defeats every deterministic algorithm because the adversary sees its cache. If the request sequence must be fixed in advance, randomized marking has expected cost within a factor of order of the optimum. This is developed in the randomized marking unit.
Summary
A recency-weighted potential rises by at most per offline fault and drops by at least one per LRU fault after the offline step. Telescoping proves the sharp factor from equal initial caches. A separate missing-page adversary rules out any smaller deterministic competitive factor, even with an additive constant.
Exercises
Quick check
(For , LRU order and offline cache , calculate the potential.)
Find the pages in the LRU cache that are not in the offline cache.
Solution · Answer
Only lies in , and its rank is one. Its weight is , so the potential is three.
Quick check
(Starting from the situation in the previous check, request and let offline hit. Give the new LRU order and calculate the new potential.)
First decide whether LRU hits or faults, then update the order.
Solution · Answer
LRU faults, evicts least-recent , and inserts at the front, giving order . The only online-only page remains , now rank two and weight two. The potential drops by one, paying for the fault.
Quick check
(In the same initial situation, suppose the offline cache changes from to while LRU's order is fixed. Calculate the potential change.)
Which page is online-only after the change, and at what rank?
Solution · Answer
Initially the potential is three. After the offline change, is in and is not, so the sole contribution is at rank two, with weight two. The potential change is . An offline change can also increase potential, but never by more than on a fault.
Quick check
(Explain why the telescoping proof allows us to discard the final potential but would need an extra term if the initial caches differed.)
Write the summed inequality and look at the potential terms.
Solution · Answer
Summation yields . The final potential is nonnegative, so removing it weakens the inequality. Equal initial caches give zero initial potential; otherwise the initial potential remains as an additive upper-bound term.