Competitive Paging Algorithms
arXiv:cs/0205038 · doi:10.1016/0196-6774(91)90041-V
Abstract
The paging problem is that of deciding which pages to keep in a memory of k pages in order to minimize the number of page faults. This paper introduces the marking algorithm, a simple randomized on-line algorithm for the paging problem, and gives a proof that its performance guarantee (competitive ratio) is O(log k). In contrast, no deterministic on-line algorithm can have a performance guarantee better than k.
Cited by in corpus (31)
- The K-Server Dual and Loose Competitiveness for Paging
- On-Line File Caching
- Ramsey-type theorems for metric spaces with applications to online problems
- On-Line Paging against Adversarially Biased Random Inputs
- Truly Online Paging with Locality of Reference
- Automating Distributed Tiered Storage Management in Cluster Computing
- Greedy D-Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost
- Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms
- Online Companion Caching
- Online Coded Caching
- Randomized k-server algorithms for growth-rate bounded graphs
- Rational Competitive Analysis
- ReNets: Toward Statically Optimal Self-Adjusting Networks
- Lower Bounds for Caching with Delayed Hits
- Dynamic Balanced Graph Partitioning
- Online Dynamic B-Matching With Applications to Reconfigurable Datacenter Networks
- Online Paging with Heterogeneous Cache Slots
- On the Incomparability of Cache Algorithms in Terms of Timing Leakage
- A Competitive Ratio Approximation Scheme for the k-Server Problem in Fixed Finite Metrics
- A Polylogarithmic-Competitive Algorithm for the k-Server Problem
- Caching with rental cost and zapping
- Competitive ratio versus regret minimization: achieving the best of both worlds
- Cache Management for Mixture-of-Experts LLMs -- extended version
- MOO: A Methodology for Online Optimization through Mining the Offline Optimum
- Optimal Online Algorithms for File-Bundle Caching and Generalization to Distributed Caching
- Paging with Multiple Caches
- Online Tree Caching
- An O(log k log^2 n)-competitive Randomized Algorithm for the k-Sever Problem
- Settling the Randomized k-sever Conjecture on Some Special Metrics
- Toward Online Mobile Facility Location on General Metrics
- Randomized Work-Competitive Scheduling for Cooperative Computing on -partite Task Graphs