dc.contributor.author | Barve, Rakesh | |
dc.contributor.author | Grove, Edward F. | |
dc.contributor.author | Vitter, Jeffrey Scott | |
dc.date.accessioned | 2011-03-16T16:45:18Z | |
dc.date.available | 2011-03-16T16:45:18Z | |
dc.date.issued | 2000 | |
dc.identifier.citation | R. D. Barve, E. F. Grove, and J. S. Vitter. “Application-Controlled Paging for a Shared Cache,” SIAM Journal on Computing, 29(4), 2000, 1290–1303. An extended abstract appears in Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science (FOCS ’95), Milwaukee, WI, October 1995, 204–213. http://dx.doi.org/10.1137/S0097539797324278 | |
dc.identifier.uri | http://hdl.handle.net/1808/7174 | |
dc.description | AMS subject classi cations. 68N25, 68P01, 68P15, 68Q25, 68W20
PII. S0097539797324278 | |
dc.description.abstract | We 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 Hk 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 2HP¡1 + 2 2 lnP. 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 minfHP¡1;Hkg, 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.language.iso | en_US | |
dc.publisher | Society for Industrial and Applied Mathematics | |
dc.subject | Caching | |
dc.subject | Application-controlled | |
dc.subject | Competitive | |
dc.subject | Online | |
dc.subject | Randomized | |
dc.title | Application-Controlled Paging for a Shared Cache | |
dc.type | Article | |
kusw.kuauthor | Vitter, Jeffrey Scott | |
kusw.oastatus | fullparticipation | |
dc.identifier.doi | 10.1137/S0097539797324278 | |
kusw.oaversion | Scholarly/refereed, publisher version | |
kusw.oapolicy | This item meets KU Open Access policy criteria. | |
dc.rights.accessrights | openAccess | |