A simple proof of optimality for the MIN cache replacement policy

Mun Kyu Lee; Pierre Michaud; Jeong Seop Sim; Dae Hun Nyang

doi:10.1016/j.ipl.2015.09.004

A simple proof of optimality for the MIN cache replacement policy

Mun Kyu Lee, Pierre Michaud, Jeong Seop Sim, Dae Hun Nyang

Department of Cyber Security

Research output: Contribution to journal › Article › peer-review

8 Scopus citations

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 (2007) [3] and Vogler (2008) [4]. We provide a simpler proof based on a novel invariant condition maintained through an incremental procedure.

Original language	English
Pages (from-to)	168-170
Number of pages	3
Journal	Information Processing Letters
Volume	116
Issue number	2
DOIs	https://doi.org/10.1016/j.ipl.2015.09.004
State	Published - Feb 2016

Bibliographical note

Publisher Copyright:
© 2015 Elsevier B.V.

Keywords

Analysis of algorithms
Caching
MIN algorithm
Paging

Access to Document

10.1016/j.ipl.2015.09.004

Cite this

@article{bd6466c88bb640ce9ccfd430069ca76a,

title = "A simple proof of optimality for the MIN cache replacement policy",

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 (2007) [3] and Vogler (2008) [4]. We provide a simpler proof based on a novel invariant condition maintained through an incremental procedure.",

keywords = "Analysis of algorithms, Caching, MIN algorithm, Paging",

author = "Lee, {Mun Kyu} and Pierre Michaud and Sim, {Jeong Seop} and Nyang, {Dae Hun}",

note = "Publisher Copyright: {\textcopyright} 2015 Elsevier B.V.",

year = "2016",

month = feb,

doi = "10.1016/j.ipl.2015.09.004",

language = "English",

volume = "116",

pages = "168--170",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - A simple proof of optimality for the MIN cache replacement policy

AU - Lee, Mun Kyu

AU - Michaud, Pierre

AU - Sim, Jeong Seop

AU - Nyang, Dae Hun

PY - 2016/2

Y1 - 2016/2

N2 - 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 (2007) [3] and Vogler (2008) [4]. We provide a simpler proof based on a novel invariant condition maintained through an incremental procedure.

AB - 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 (2007) [3] and Vogler (2008) [4]. We provide a simpler proof based on a novel invariant condition maintained through an incremental procedure.

KW - Analysis of algorithms

KW - Caching

KW - MIN algorithm

KW - Paging

UR - http://www.scopus.com/inward/record.url?scp=84949094879&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2015.09.004

DO - 10.1016/j.ipl.2015.09.004

M3 - Article

AN - SCOPUS:84949094879

SN - 0020-0190

VL - 116

SP - 168

EP - 170

JO - Information Processing Letters

JF - Information Processing Letters

IS - 2

ER -

A simple proof of optimality for the MIN cache replacement policy

Abstract

Bibliographical note

Keywords

Access to Document

Fingerprint

Cite this