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.
Type de document :
Article dans une revue
Information Processing Letters, Elsevier, 2015, pp.3. 〈10.1016/j.ipl.2015.09.004〉
Liste complète des métadonnées

Littérature citée [4 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01199424
Contributeur : Pierre Michaud <>
Soumis le : mercredi 14 octobre 2015 - 15:16:47
Dernière modification le : mercredi 11 avril 2018 - 02:00:19
Document(s) archivé(s) le : jeudi 27 avril 2017 - 04:37:49

Fichier

halversion.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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〉

Partager

Métriques

Consultations de la notice

346

Téléchargements de fichiers

165