A simple proof of optimality for the MIN cache replacement policy
Résumé
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.
Domaines
Architectures Matérielles [cs.AR]
Origine : Fichiers produits par l'(les) auteur(s)
Loading...