Competitive analysis of online paging algorithms may be based on a flawed model assumption
By
[Submitted on 22 Jun 2026]
Summary
This academic paper argues that the Sleator-Tarjan model underlying competitive analysis of online paging algorithms contains a fundamental flaw: it charges a cost for the first access to newly computed data, whereas in real systems, data begins in the processor and incurs no cold miss. The authors show that correcting this model means no online paging algorithm (including LRU) can be competitive, even with randomization or resource augmentation. They suggest that competitive analysis's predictions of good performance for algorithms like LRU are a fortuitous artifact of an incorrect assumption. The paper also notes implications beyond paging, undermining the Ideal Cache model used in Cache-Oblivious and Cache-Adaptive frameworks.
Source
bskyCompetitive analysis of online paging algorithms may be based on a flawed model assumptionarxiv.orgKey quotes
· 4 pulledIn any real system a newly computed datum begins its existence in the processor rather than in external memory, and thus does not inevitably incur a cold miss.
If one corrects the Sleator-Tarjan model by charging no cost for the first access to newly computed data, optimal offline algorithms such as LFD remain optimal, but no online paging algorithm can be competitive.
Competitive analysis does predict the good performance exhibited in practice by online paging algorithms such as LRU, these predictions seem just a fortuitous artifact of an incorrect assumption that has crept into the underlying model several decades ago.
The same issue undermines the Ideal Cache model on which the popular Cache-Oblivious and Cache-Adaptive algorithmic frameworks are based.
You might also wanna read
The Mathematics of Data Structures: Why No Single Storage Solution Is Optimal
The article explores the fundamental trade-offs in data structure design, explaining that there's no single optimal way to store information
quantamagazine.org·5mo ago
Disk Access Outperforms Memory Caching in Modern Hardware Systems
This technical article challenges conventional computer science wisdom by demonstrating that sourcing data directly from disk can be faster
bitflux.ai·10mo ago
Local-First Information Retrieval: Keeping Search Private on Consumer Hardware
This paper proposes "local-first IR" (information retrieval), a design philosophy where search indexes, models, and inference all reside on
arxiv.org·4d ago
Understanding Linux Memory Management: Page Faults, mmap, and userfaultfd
This technical article explores Linux memory management concepts including page faults, mmap system calls, and userfaultfd. The author expla
shayon.dev·3mo agoTechnical Analysis of Robin Hood Hash Table Implementation with Linear Probing
The article presents a technical discussion of a specific hash table implementation called "Robin Hood open-addressing with linear probing a
The Evolution of Performance Optimization: From CPU Instructions to Data Structure Design
The article discusses how performance optimization has evolved from focusing on micro-level instruction optimization to data structure desig
tedinski.com·7mo ago
Comments
Sign in to join the conversation.
No comments yet. Be the first.