k-competitive is useless advice for a large cache, so the lecture lists three escape routes (1:06:11, 1:07:41).
1. Limited associativity
- Real caches are often only partially associative: a given page may live in only a few slots (
1:08:08). - Then the competitive ratio scales with the associativity, not the full cache size — a much smaller number (
1:08:36). - Fully non-associative caches leave nothing to analyse (
1:08:08).
2. Resource augmentation
- Also introduced in Sleator–Tarjan: give the algorithm
kslots and OPT onlyk′ ≤ kslots (1:08:54). - Result: LRU and FIFO are
k / (k − k′ + 1)-competitive (1:09:41). - Consequence: with
k′ = k/2, LRU is roughly 2-competitive against the halved-memory adversary — weakening the omniscient adversary slightly buys a much better ratio (1:09:41,1:10:20).
3. Randomization — and which adversary you face
- The lower bound relies on an adversary who knows what you will evict; a random victim breaks that construction (
1:10:48). - So one must classify adversaries (
1:11:28):
| Adversary | Knowledge | Effect on randomization |
|---|---|---|
| Omniscient | Knows everything, including future coin flips (1:11:28) | You are effectively deterministic; randomness does not help (1:12:08) |
| Adaptive | Knows past coin flips and all past accesses; picks the next request from that (1:12:08, 1:12:35) | Still hopeless: it knows what is not in your cache right now and asks for it (1:13:16) |
| Oblivious | Fixes the whole sequence S before any coin is flipped; not trying to hurt you (1:12:35, 1:13:16) | The k lower bound says nothing here — this is where randomization pays (1:14:20) |