Article

Free access

Randomized and multipointer paging with locality of reference

Authors:

Amos Fiat,

Anna R. KarlinAuthors Info & Claims

STOC '95: Proceedings of the twenty-seventh annual ACM symposium on Theory of computing

Pages 626 - 634

https://doi.org/10.1145/225058.225280

Published: 29 May 1995 Publication History

PDF eReader

References

[1]

L .A. Belady. A study of replacement algorithms for virtual storage computers. IBM SysterrM Jovr-nal, 5:78-101, 1966.

Digital Library

Google Scholar

[2]

A. Borodin, S. Irani, P. Raghavan, and B. Schieber. Competitive Paging with Locality of Reference. In Proc. 25'rrl Annual ACM Syrn-posiwna on Theory of Computing, pages 249-259, 1991.

Digital Library

Google Scholar

[3]

P. J. Denning. Working sets past and present. IEEE Trans. Software Engg., SE-6:64--84, 198(1.

Digital Library

Google Scholar

[4]

A. Fiat, R. Karp, M. Luby, L. McGeoch, D. Sleator, and N. Young. Competitive paging algorithms Journal of A/gorzthms, 12(4):685-699, 1991.

Digital Library

Google Scholar

[5]

P.A. Franaszek and T. J. Wagner, Some distribution-free aspects of paging performance. Journal of the ACM, 21:31-39, 1974.

Digital Library

Google Scholar

[6]

K. Harty and D. Cheriton. Application-controlled physical memory using external page-cache man-agement. In Proceedings of the 5t,h Interna-tional Conference on Architectural Support for Programming Languages and Operating Systems, 1992.

Digital Library

Google Scholar

[7]

S. Irani, A.R. Karlin and S. Phillips. Strongly competitive algorithms for paging with locality of reference. In Proceedings of the Third Annual ACM-SIAM Symposium on Dzscrete Algorithms, 1992.

Digital Library

Google Scholar

[8]

A. R. Karlin, M. S. Manasse, L. Rudolph, and D.D. Sleator. Competitive snoopy caching. Algo-rithmtca, 3(1):70-119, 1988.

Google Scholar

[9]

A. R. Karlin, S. Phillips, and P. Raghavan. Markov paging. In Proceedings of $'t?rd Annual Symposiwm on Foundations of Computer Science, 1992.

Digital Library

Google Scholar

[10]

T. Kilburn, D.B. G. Edwards, M.J. Lanigan, and F.H. Sumner. One-level storage system. IRE Trans. Elect. Computers, 37:223-235, 1962.

Crossref

Google Scholar

[11]

E. Koutsoupias and C. Papadirnitriou. Beyond competitive analysis. In Proceedings of 35rd An-nual Symposium on Foundations of Computer Science, 1994.

Digital Library

Google Scholar

[12]

C. Lund, S. Phillips and N. Reingold. IP-paging and distributional paging. In Proceedings of 35rd Annual Symposium on Foundations oj Computer Sc8ence, 1994.

Google Scholar

[13]

M.S. Manasse, L.A. McGeoch, and D.D. Sleator. Competitive algorithms for on-line problems. Journal of Algorithms, 11:208-230, 1990.

Digital Library

Google Scholar

[14]

L.A. McGeoch and D.D. Sleator. A strongly com-petitive randomized paging algorithm. Algorith-mic, 6(6):816-825, 1991.

Digital Library

Google Scholar

[15]

D. McNamee and K. Armstrong. Extending the Mach external pager interface to aceomrnoclate user-level page replacement policies, In Pro-ceedings of the First USENIX Mach Symposium, 1990.

Google Scholar

[16]

P. Raghavan and M. Snir. Memory versus ran-domiz at ion in on-line algorithms. In Proceedings of 16th International Colloquium on Automata, Languages and Programming, 1989,

Digital Library

Google Scholar

[17]

G.S. Shedler and C. Tung. Locality in page ref-erence strings. SIAM Journal on Computing, 1:218-241, 1972.

Crossref

Google Scholar

[18]

D.D. Sleator and R.E. Tarjan. Amortized effi-ciency of list update and paging rules. Co mmun i-cations of the ACM, 28:202-208, February 1985.

Digital Library

Google Scholar

[19]

J.R. Spirn. Program Behavior: Models and Mea-surements. Elsevier Computer Science Library. Elsevier, Amsterdam, 1977.

Digital Library

Google Scholar

[20]

AC. Yao. Probabilistic Computations: Towards a unifed measure of complexity. In Proceedings o~ the 18th Annual Symposium on Foundations of Computer Science, 1977.

Google Scholar

Cited By

View all

Agrawal KBender MDas RKuszmaul WPeserico EScquizzato MAgrawal KLee I(2022)Online Parallel Paging with Optimal MakespanProceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3490148.3538577(205-216)Online publication date: 11-Jul-2022
https://dl.acm.org/doi/10.1145/3490148.3538577
Agrawal KBender MDas RKuszmaul WPeserico EScquizzato MMarx D(2021)Tight bounds for parallel paging and green pagingProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458244(3022-3041)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458244
López-Ortiz ASalinger A(2014)Analyzing Cache Behaviour in Multicore ArchitecturesEncyclopedia of Algorithms10.1007/978-3-642-27848-8_534-1(1-6)Online publication date: 13-Oct-2014
https://doi.org/10.1007/978-3-642-27848-8_534-1
Show More Cited By

Index Terms

Randomized and multipointer paging with locality of reference
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Trees
  2. Probability and statistics
    1. Probabilistic algorithms
    2. Probabilistic reasoning algorithms
      1. Markov-chain Monte Carlo methods
      2. Sequential Monte Carlo methods
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Competitive Paging with Locality of Reference
Selected papers of the 23rd annual ACM symposium on Theory of computing

The Sleator-Tarjan competitive analysis of paging (Comm. ACM28 (1985), 202-208) gives us the ability to make strong theoretical statements about the performance of paging algorithms without making probabilistic assumptions on the input. Nevertheless ...
Competitive Paging with Locality of Reference

The Sleator-Tarjan competitive analysis of paging (Comm. ACM28 (1985), 202-208) gives us the ability to make strong theoretical statements about the performance of paging algorithms without making probabilistic assumptions on the input. Nevertheless ...
Quantifying Competitiveness in Paging with Locality of Reference

The classical paging problem is to maintain a two-level memory system so that a sequence of requests to memory pages can be served with a small number of faults. Standard competitive analysis gives overly pessimistic results as it ignores the fact that ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '95: Proceedings of the twenty-seventh annual ACM symposium on Theory of computing

May 1995

776 pages

ISBN:0897917189

DOI:10.1145/225058

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 May 1995

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC95

Sponsor:

SIGACT

STOC95: Symposium on Theory of Computing

May 29 - June 1, 1995

Nevada, Las Vegas, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

32
Total Citations
View Citations
337
Total Downloads

Downloads (Last 12 months)57
Downloads (Last 6 weeks)5

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Agrawal KBender MDas RKuszmaul WPeserico EScquizzato MAgrawal KLee I(2022)Online Parallel Paging with Optimal MakespanProceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3490148.3538577(205-216)Online publication date: 11-Jul-2022
https://dl.acm.org/doi/10.1145/3490148.3538577
Agrawal KBender MDas RKuszmaul WPeserico EScquizzato MMarx D(2021)Tight bounds for parallel paging and green pagingProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458244(3022-3041)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458244
López-Ortiz ASalinger A(2014)Analyzing Cache Behaviour in Multicore ArchitecturesEncyclopedia of Algorithms10.1007/978-3-642-27848-8_534-1(1-6)Online publication date: 13-Oct-2014
https://doi.org/10.1007/978-3-642-27848-8_534-1
Ausiello GBecchetti L(2014)On‐Line AlgorithmsParadigms of Combinatorial Optimization10.1002/9781119005353.ch15(473-509)Online publication date: 8-Aug-2014
https://doi.org/10.1002/9781119005353.ch15
(2014)General BibliographyParadigms of Combinatorial Optimization10.1002/9781119005353.biblio(707-765)Online publication date: 8-Aug-2014
https://doi.org/10.1002/9781119005353.biblio
Ausiello GBecchetti L(2013)On‐Line AlgorithmsParadigms of Combinatorial Optimization10.1002/9781118600207.ch15(473-509)Online publication date: 13-Feb-2013
https://doi.org/10.1002/9781118600207.ch15
Moruz GNegoescu A(2012)Outperforming LRU via competitive analysis on parametrized inputs for pagingProceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms10.5555/2095116.2095248(1669-1680)Online publication date: 17-Jan-2012
https://dl.acm.org/doi/10.5555/2095116.2095248
López-Ortiz ASalinger AGoldwasser S(2012)Paging for multi-core shared cachesProceedings of the 3rd Innovations in Theoretical Computer Science Conference10.1145/2090236.2090246(113-127)Online publication date: 8-Jan-2012
https://dl.acm.org/doi/10.1145/2090236.2090246
Boyar JGupta SLarsen K(2012)Access graphs results for LRU versus FIFO under relative worst order analysisProceedings of the 13th Scandinavian conference on Algorithm Theory10.1007/978-3-642-31155-0_29(328-339)Online publication date: 4-Jul-2012
https://dl.acm.org/doi/10.1007/978-3-642-31155-0_29
Emek YFraigniaud PKorman ARosén A(2011)Online computation with adviceTheoretical Computer Science10.1016/j.tcs.2010.08.007412:24(2642-2656)Online publication date: 1-May-2011
https://dl.acm.org/doi/10.1016/j.tcs.2010.08.007
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Competitive Paging with Locality of Reference

Competitive Paging with Locality of Reference

Quantifying Competitiveness in Paging with Locality of Reference