Critical sizing of LRU caches with dependent requests

DOI10.1239/JAP/1165505204MaRDI QIDQ5441519zbMATH OpenOpenAlexFDO

Authors Predrag R. Jelenković, Ana Radovanović, Mark S. Squillante

Publication date 15 February 2008

Published in Journal of Applied Probability (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1239/jap/1165505204

zbMATH Keywords

least-recently-used caching policysemi-Markov-modulated requests

Mathematics Subject Classification ID

Large deviations (60F10) Sums of independent random variables; random walks (60G50) Continuous-time Markov processes on general state spaces (60J25) Searching and sorting (68P10)

Recommendations

• LRU caching with moderately heavy request distributions
• Optimizing LRU Caching for Variable Document Sizes
• Analysis of LRU cache trees with a power law reference distribution
• Least-recently-used caching with dependent requests
• Size-Aware Cache Management for Compressed Cache Architectures
• A new approach to optimal cache scheduling
• Mixed-criticality scheduling with dynamic redistribution of shared cache

Cites work

• An exact formula for the move-to-front rule for self-organizing lists
• Asymptotic approximation of the move-to-front search cost distribution and least-recently used caching fault probabilities
• Birthday paradox, coupon collectors, caching algorithms and self- organizing search
• scientific article; zbMATH DE number 410740 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 903457 (Why is no real title available?)
• Large claims approximations for risk processes in a Markovian environment
• Least-recently-used caching with dependent requests
• On-Line Paging Against Adversarially Biased Random Inputs
• Optimizing LRU Caching for Variable Document Sizes
• Self-adjusting binary search trees
• Subexponential asymptotics of a Markov-modulated random walk with queueing applications

Cited in

(8)

• Asymptotic optimality of the static frequency caching in the presence of correlated requests
• Optimal timer-based caching policies for general arrival processes
• Approximate analysis of LRU in the case of short term correlations
• A fluid limit for a cache algorithm with general request processes
• On the asymptotics of fault probability in least-recently-used caching with Zipf-type request distribution
• LRU caching with moderately heavy request distributions
• Asymptotic optimality of the static frequency caching in the presence of correlated requests
• Least-recently-used caching with dependent requests

This page was built for publication: Critical sizing of LRU caches with dependent requests

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