Published in

Elsevier, Information Processing Letters, 2(116), p. 168-170, 2016

DOI: 10.1016/j.ipl.2015.09.004

Links

Tools

Export citation

Search in Google Scholar

A simple proof of optimality for the MIN cache replacement policy

Journal article published in 2015 by Mun-Kyu Lee, Pierre Michaud, Jeong Seop Sim, DaeHun Nyang
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
Orange circle
Postprint: archiving restricted
Red circle
Published version: archiving forbidden
Data provided by SHERPA/RoMEO

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.