Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1109/SFCS.1986.14guideproceedingsArticle/Chapter ViewAbstractPublication PagesConference Proceedingsacm-pubtype
Article

Competitive snoopy caching

Published: 27 October 1986 Publication History

Abstract

In a snoopy cache multiprocessor system, each processor has a cache in which it stores blocks of data. Each cache is connected to a bus used to communicate with the other caches and with main memory. For several of the proposed models of snoopy caching, we present new on-line algorithms which decide, for each cache, which blocks to retain and which to drop in order to minimize communication over the bus. We prove that, for any sequence of operations, our algorithms' communication costs are within a constant factor of the minimum required for that sequence; for some of our algorithms we prove that no on-line algorithm has this property with a smaller constant.

Cited By

View all
  • (2023)λFS: A Scalable and Elastic Distributed File System Metadata Service using Serverless FunctionsProceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 410.1145/3623278.3624765(394-411)Online publication date: 25-Mar-2023
  • (2023)An Associativity Threshold Phenomenon in Set-Associative CachesProceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3558481.3591084(117-127)Online publication date: 17-Jun-2023
  • (2020)The primal-dual method for learning augmented algorithmsProceedings of the 34th International Conference on Neural Information Processing Systems10.5555/3495724.3497410(20083-20094)Online publication date: 6-Dec-2020
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings
SFCS '86: Proceedings of the 27th Annual Symposium on Foundations of Computer Science
October 1986
516 pages
ISBN:0818607408

Publisher

IEEE Computer Society

United States

Publication History

Published: 27 October 1986

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 10 Nov 2024

Other Metrics

Citations

Cited By

View all
  • (2023)λFS: A Scalable and Elastic Distributed File System Metadata Service using Serverless FunctionsProceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 410.1145/3623278.3624765(394-411)Online publication date: 25-Mar-2023
  • (2023)An Associativity Threshold Phenomenon in Set-Associative CachesProceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3558481.3591084(117-127)Online publication date: 17-Jun-2023
  • (2020)The primal-dual method for learning augmented algorithmsProceedings of the 34th International Conference on Neural Information Processing Systems10.5555/3495724.3497410(20083-20094)Online publication date: 6-Dec-2020
  • (2018)The Transactional Conflict ProblemProceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures10.1145/3210377.3210406(383-392)Online publication date: 11-Jul-2018
  • (2018)An Online Algorithm for Task Offloading in Heterogeneous Mobile CloudsACM Transactions on Internet Technology10.1145/312298118:2(1-25)Online publication date: 20-Jan-2018
  • (2017)Makespan Minimization via Posted PricesProceedings of the 2017 ACM Conference on Economics and Computation10.1145/3033274.3085129(405-422)Online publication date: 20-Jun-2017
  • (2016)Online Algorithms with Advice: A SurveyACM SIGACT News10.1145/2993749.299376647:3(93-129)Online publication date: 31-Aug-2016
  • (2016)Online matching: haste makes waste!Proceedings of the forty-eighth annual ACM symposium on Theory of Computing10.1145/2897518.2897557(333-344)Online publication date: 19-Jun-2016
  • (2009)The Design of Competitive Online Algorithms via a PrimalFoundations and Trends® in Theoretical Computer Science10.1561/04000000243:2–3(93-263)Online publication date: 1-Feb-2009
  • (2009)The k-server problemComputer Science Review10.1016/j.cosrev.2009.04.0023:2(105-118)Online publication date: 1-May-2009
  • Show More Cited By

View Options

View options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media