Don't Melt Your Cache: Low-Associativity with Heat-Sink
Perhaps the most influential result in the theory of caches is the following theorem due to Sleator and Tarjan: With O(1) resource augmentation, the basic LRU eviction policy is guaranteed to be O(1)-competitive with the optimal offline policy.
Authors
- William Kuszmaul (ORCID: https://orcid.org/0000-0002-3855-3036)
- Evan West (ORCID: https://orcid.org/0000-0002-5974-7745)
- Jaehyun Han (ORCID: https://orcid.org/0000-0002-6052-7889)
- Michael A. Bender (ORCID: https://orcid.org/0000-0001-7639-530X)
- Sudarsun Kannan (ORCID: https://orcid.org/0000-0003-4009-8586)
- Donald E. Porter (ORCID: https://orcid.org/0000-0002-9804-0857)
- Daniel DeLayo (ORCID: https://orcid.org/0000-0001-7636-0107)
- Alex Conway (ORCID: https://orcid.org/0000-0003-4890-7413)
- Martı́n Farach-Colton (ORCID: https://orcid.org/0000-0003-3616-7788)
- Linfeng He
- Rob Johnson (ORCID: https://orcid.org/0000-0002-0784-7410)
Institutions
- Rutgers, The State University of New Jersey (US)
- University of North Carolina at Chapel Hill (US)
- Cornell University (US)
- New York University (US)
- Stony Brook University (US)
- Kitware (United States) (US)
- Carnegie Mellon University (US)
Publication Details
- Published
- 2025-07-16
- DOI
- https://doi.org/10.1145/3694906.3743303
- Primary Topic
- Optimization and Search Problems
- Type
- article
- Field-Weighted Citation Impact
- 0.00