{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,16]],"date-time":"2026-10-16T13:14:14Z","timestamp":1792156454025,"version":"4.4.0"},"reference-count":8,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2000,1]]},"abstract":"<jats:p>\n                    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 $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{H\n                    <jats:sub>P-1<\/jats:sub>\n                    ,H\n                    <jats:sub>k<\/jats:sub>\n                    }, 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.\n                  <\/jats:p>\n                  <jats:p>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.<\/jats:p>","DOI":"10.1137\/s0097539797324278","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1290-1303","source":"Crossref","is-referenced-by-count":11,"title":["Application-Controlled Paging for a Shared Cache"],"prefix":"10.1137","volume":"29","author":[{"given":"Rakesh D.","family":"Barve","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Edward F.","family":"Grove","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jeffrey Scott","family":"Vitter","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,27]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1147\/sj.52.0078"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1021"},{"key":"R3","unstructured":"P. Cao, E. W. Felten, and K. Li,\n                      Application\u2010controlled file caching policies\n                      , in Proceedings of the Summer USENIX Conference, Boston, MA, 1994, pp. 171\u2013182."},{"key":"R4","unstructured":"P. Cao, E. W. Felten, and K. Li,\n                      Implementation and performance of application\u2010contolled file caching\n                      , in Proceedings of the First OSDI Symposium, Monterey, CA, 1994, pp. 165\u2013177."},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90041-V"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"A. R. Karlin, S. J. Phillips, and P. Raghavan,\n                      Markov paging\n                      , in Proceedings of the 33rd Annual IEEE Conference on Foundations of Computer Science, Pittsburgh, PA, 1992, pp. 208\u2013217.","DOI":"10.1109\/SFCS.1992.267771"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1007\/BF01759073"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539797324278","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:13:30Z","timestamp":1787336010000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539797324278"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,1]]},"references-count":8,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2000,1]]}},"alternative-id":["10.1137\/S0097539797324278"],"URL":"https:\/\/doi.org\/10.1137\/s0097539797324278","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000,1]]}}}