Critical sizing of LRU caches with dependent requests

DOI10.1239/jap/1165505204zbMath1137.68023OpenAlexW2091996079MaRDI QIDQ5441519

Ana Radovanović, Predrag R. Jelenković, 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

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

Related Items

Optimal timer-based caching policies for general arrival processes ⋮ A fluid limit for a cache algorithm with general request processes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Least-recently-used caching with dependent requests
• Birthday paradox, coupon collectors, caching algorithms and self- organizing search
• Asymptotic approximation of the move-to-front search cost distribution and least-recently used caching fault probabilities
• Large claims approximations for risk processes in a Markovian environment
• An exact formula for the move-to-front rule for self-organizing lists
• Self-adjusting binary search trees
• Subexponential asymptotics of a Markov-modulated random walk with queueing applications
• On-Line Paging Against Adversarially Biased Random Inputs
• Optimizing LRU Caching for Variable Document Sizes