In any real system, newly computed data begins its existence in the processor rather than in external memory, thus not inevitably incurring a cold miss. This was captured by early I/O models but not by the Sleator-Tarjan model that underpins competitive analysis of paging.
If one corrects the Sleator-Tarjan model by charging no cost for the first access to newly computed data, optimal offline algorithms like LFD remain optimal; however, no online paging algorithm can be competitive, even if randomized, and even with arbitrary resource augmentation against request sequences that are representative of widely used computational techniques.
The proofs are simple and robust against any reasonable assumption/model adjustment, including virtually all tools developed to make competitive analysis less pessimistic. In other words, while competitive analysis predicts the good performance exhibited in practice by online paging algorithms like LRU, these predictions seem to be a fortuitous artifact of an incorrect assumption that has crept into the underlying model decades ago. This issue also undermines the Ideal Cache model on which popular Cache-Oblivious and Cache-Adaptive algorithmic frameworks are based.
Blogger's Review: This research delves deeply into the theoretical foundations of online paging algorithms, revealing potential flaws in model assumptions. While traditional competitive analysis often effectively guides algorithm design in practice, the fragility of its theoretical basis prompts caution in algorithm research, especially in the face of emerging computational technologies.