On-Line Paging Against Adversarially Biased Random Inputs

DOI10.1006/JAGM.2000.1099MaRDI QIDQ4512578zbMATH OpenOpenAlexFDO

Authors Neal E. Young

Publication date 30 October 2001

Published in Journal of Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/cs/0205007

zbMATH Keywords

paging strategy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Abstract: In evaluating an algorithm, worst-case analysis can be overly pessimistic. Average-case analysis can be overly optimistic. An intermediate approach is to show that an algorithm does well on a broad class of input distributions. Koutsoupias and Papadimitriou recently analyzed the least-recently-used (LRU) paging strategy in this manner, analyzing its performance on an input sequence generated by a so-called diffuse adversary -- one that must choose each request probabilitistically so that no page is chosen with probability more than some fixed epsilon>0. They showed that LRU achieves the optimal competitive ratio (for deterministic on-line algorithms), but they didn't determine the actual ratio. In this paper we estimate the optimal ratios within roughly a factor of two for both deterministic strategies (e.g. least-recently-used and first-in-first-out) and randomized strategies. Around the threshold epsilon ~ 1/k (where k is the cache size), the optimal ratios are both Theta(ln k). Below the threshold the ratios tend rapidly to O(1). Above the threshold the ratio is unchanged for randomized strategies but tends rapidly to Theta(k) for deterministic ones. We also give an alternate proof of the optimality of LRU.

Recommendations

• On the separation and equivalence of paging strategies
• On adequate performance measures for paging
• Competitive analysis of randomized paging algorithms
• Quantifying competitiveness in paging with locality of reference
• Quantifying competitiveness in paging with locality of reference

Cited in

(23)

• More on randomized on-line algorithms for caching.
• Competitive analysis of the LRFU paging algorithm
• The worst page-replacement policy
• Stochastic dominance and the bijective ratio of online algorithms
• Parameterized analysis of paging and list update algorithms
• Relative interval analysis of paging algorithms on access graphs
• The complexity of paging against a probabilistic adversary
• On the separation and equivalence of paging strategies
• Online network design with outliers
• Paging and list update under bijective analysis
• scientific article; zbMATH DE number 1830729 (Why is no real title available?)
• Measuring the problem-relevant information in input
• On the Relative Dominance of Paging Algorithms
• Paging and list update under bijective analysis
• The Worst Page-Replacement Policy
• Critical sizing of LRU caches with dependent requests
• Closing the Gap Between Theory and Practice: New Measures for On-Line Algorithm Analysis
• Outperforming LRU via competitive analysis on parametrized inputs for paging
• Approximating \(k\)-forest with resource augmentation: a primal-dual approach
• A theoretical comparison of LRU and LRU-K
• On the separation and equivalence of paging strategies and other online algorithms
• On the relative dominance of paging algorithms
• The relative worst-order ratio applied to paging

This page was built for publication: On-Line Paging Against Adversarially Biased Random Inputs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4512578)