Show simple item record

dc.contributor.authorBarve, Rakesh
dc.contributor.authorGrove, Edward F.
dc.contributor.authorVitter, Jeffrey Scott
dc.identifier.citationBarve, Rakesh D., Edward F. Grove, and Jeffrey Scott Vitter. "Application-Controlled Paging for a Shared Cache." SIAM J. Comput. SIAM Journal on Computing 29.4 (2000): 1290-303. DOI:10.1137/S0097539797324278en_US
dc.descriptionThis is the published version. Copyright © 2000 Society for Industrial and Applied Mathematicsen_US
dc.description.abstractWe propose a provably efficient application-controlled global strategy for organizing a cache of size k shared among P application processes. Each application has access to information about its own future page requests, and by using that local information along with randomization in the context of a global caching algorithm, we are able to break through the conventional $H_k \sim \ln k$ lower bound on the competitive ratio for the caching problem. If the P application processes always make good cache replacement decisions, our online application-controlled caching algorithm attains a competitive ratio of $2H_{P-1}+2 \sim 2 \ln P$. Typically, P is much smaller than k, perhaps by several orders of magnitude. Our competitive ratio improves upon the 2P+2 competitive ratio achieved by the deterministic application-controlled strategy of Cao, Felten, and Li. We show that no online application-controlled algorithm can have a competitive ratio better than min{HP-1 ,Hk}, even if each application process has perfect knowledge of its individual page request sequence. Our results are with respect to a worst-case interleaving of the individual page request sequences of the P application processes.

We introduce a notion of fairness in the more realistic situation when application processes do not always make good cache replacement decisions. We show that our algorithm ensures that no application process needs to evict one of its cached pages to service some page fault caused by a mistake of some other application. Our algorithm not only is fair but remains efficient; the global paging performance can be bounded in terms of the number of mistakes that application processes make.
dc.publisherSociety for Industrial and Applied Mathematicsen_US
dc.subjectApplication controlleden_US
dc.titleApplication-Controlled Paging for a Shared Cacheen_US
kusw.kuauthorVitter, Jeffrey Scott
kusw.kudepartmentElectrical Engr & Comp Scienceen_US
kusw.oanotesPer SHERPA/RoMEO, 11/20/2015: Author's Pre-print: green tick author can archive pre-print (ie pre-refereeing) Author's Post-print: green tick author can archive post-print (ie final draft post-refereeing) Publisher's Version/PDF: green tick author can archive publisher's version/PDF General Conditions:

Author's post-print on pre-print servers, including arXiv Publisher's version/PDF on authors personal website,institutional website or open access repository Non-commercial use Publisher copyright must be acknowledged Publisher's version/PDF may be used
kusw.oaversionScholarly/refereed, publisher version
kusw.oapolicyThis item does not meet KU Open Access policy criteria.

Files in this item


This item appears in the following Collection(s)

Show simple item record