A simple proof of optimality for the MIN cache replacement policy

Mun-Kyu Lee 1 Pierre Michaud 2 Jeong Seop Sim 1 Daehun Nyang 1
2 ALF - Amdahl's Law is Forever
Inria Rennes – Bretagne Atlantique , IRISA-D3 - ARCHITECTURE
Abstract : The MIN cache replacement algorithm is an optimal off-line policy to decide which item to evict when a new item should be fetched into a cache. Recently, two short proofs were given by van Roy and Vogler.. We provide a simpler proof based on a novel invariant condition maintained through an incremental procedure.
Document type :
Journal articles
Complete list of metadatas

Cited literature [4 references]  Display  Hide  Download

https://hal.inria.fr/hal-01199424
Contributor : Pierre Michaud <>
Submitted on : Wednesday, October 14, 2015 - 3:16:47 PM
Last modification on : Thursday, February 7, 2019 - 4:21:17 PM
Long-term archiving on : Thursday, April 27, 2017 - 4:37:49 AM

File

halversion.pdf
Files produced by the author(s)

Identifiers

Citation

Mun-Kyu Lee, Pierre Michaud, Jeong Seop Sim, Daehun Nyang. A simple proof of optimality for the MIN cache replacement policy. Information Processing Letters, Elsevier, 2015, pp.3. ⟨10.1016/j.ipl.2015.09.004⟩. ⟨hal-01199424⟩

Share

Metrics

Record views

490

Files downloads

452