Competitive analysis of randomized pagin
β
Dimitris Achlioptas; Marek Chrobak; John Noga
π
Article
π
2000
π
Elsevier Science
π
English
β 130 KB
The paging problem is deΓΏned as follows: we are given a two-level memory system, in which one level is a fast memory, called cache, capable of holding k items, and the second level is an unbounded but slow memory. At each given time step, a request to an item is issued. Given a request to an item p,