Skip to Main content Skip to Navigation
New interface
Journal articles

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 metadata

Cited literature [4 references]  Display  Hide  Download
Contributor : Pierre Michaud Connect in order to contact the contributor
Submitted on : Wednesday, October 14, 2015 - 3:16:47 PM
Last modification on : Thursday, January 20, 2022 - 4:19:47 PM
Long-term archiving on: : Thursday, April 27, 2017 - 4:37:49 AM


Files produced by the author(s)



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



Record views


Files downloads