The two results

  • Upper bound (Sleator–Tarjan): LRU and FIFO are k-competitive, k = cache size (51:42).
  • Sounds terrible for an 8 GB memory — a huge competitive ratio (51:42, 52:47).
  • Lower bound (same paper): no online (deterministic) algorithm can have competitive ratio below k (52:47).

Proof of the lower bound

  • Restrict the universe to k + 1 pages, so the cache always misses exactly one page (53:53).
  • The adversary always requests the page the algorithm just evicted ⇒ a page fault on every access (54:19, 55:25).
  • OPT, evicting the page requested farthest in the future, faults at most once every k accesses — because that victim must have at least k other requests ahead of it (54:45, 55:25).
  • Ratio: k (55:25).

k-competitiveness is not automatic

  • Not every policy achieves ratio k: LFU has an unbounded competitive ratio — there are sequences where OPT pays about 1 and LFU faults essentially on every request (56:10, 56:34).

One-bit LRU (the marking scheme)

Rather than analysing LRU directly, the lecture analyses a relaxation (57:29):

  1. Initially all pages unmarked (58:22).
  2. Mark every accessed page.
  3. On an eviction, evict any unmarked page (choice unspecified/arbitrary) (58:22, 59:32).
  4. If all pages are marked and an eviction is needed, clear all mark bits, then evict and bring in the new page marked (1:00:01).

LRU is a special case of one-bit LRU, so one-bit LRU being k-competitive implies LRU is (1:01:09, 1:01:38):

  • The least recently used page is always at least k accesses in the past, so it belongs to the previous marking phase and is therefore always unmarked — a legal victim (1:02:29, 1:02:49).

Phase argument (the whole proof)

  • A phase is the interval between two consecutive "clear all bits" operations (1:03:39).
  • Starting a new phase requires k + 1 distinct pages to have been accessed, so even OPT — which also holds only k pages — faults at least once per phase (1:04:19, 1:04:50).
  • One-bit LRU faults at most k times per phase: each fault raises the number of marked pages by exactly one, and the phase ends at k marks (1:05:20, 1:06:26, 1:06:49).
  • A student correction: it is "at most k", not "exactly k", because a page surviving from the previous phase can get marked by a hit without a fault (1:07:20).
  • ≤ k faults vs ≥ 1 fault per phase ⇒ k-competitive (1:05:45).