Optimal eviction policies for stochastic address traces

DOI10.1016/j.tcs.2013.01.016zbMath1277.68022arXiv1109.6643OpenAlexW2121243500MaRDI QIDQ386897

Francesco Versaci, Gianfranco Bilardi

Publication date: 11 December 2013

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

optimal controlMarkov chainsmultiobjective optimizationpagingonline problemsalgorithms and data structureseviction policies

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Mathematical problems of computer architecture (68M07) Applications of queueing theory (congestion, allocation, storage, traffic, etc.) (60K30) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of selection and ranking in X+Y and matrices with sorted columns
• Nonlinear multiobjective optimization
• Minimization of demand paging for the LRU stack model of program behavior
• Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis.
• Competitive paging with locality of reference
• Horizons of parallel computation
• An efficient algorithm for determining the convex hull of a finite planar set
• On adequate performance measures for paging
• Some Distribution-Free Aspects of Paging Algorithm Performance
• Dynamic storage allocation in the Atlas computer, including an automatic use of a backing store
• The Complexity of Markov Decision Processes
• LRU Stack Processing
• Use of the LRU stack depth distribution for simulation of paging behavior
• Beyond Competitive Analysis
• Markov Paging
• Discrete-Time Controlled Markov Processes with Average Cost Criterion: A Survey
• Multicriteria Optimization
• Discrete Dynamic Programming
• Algorithms – ESA 2004
• The working set model for program behavior
• A model of memory contention in a paging machine
• On paging with locality of reference