Latency Guarantees for Caching with Delayed Hits
Keerthana Gurushankar, Noah G. Singer, Bernardo Subercaseaux · 2025
Read Latency Guarantees for Caching with Delayed Hits by Keerthana Gurushankar, Noah G. Singer, Bernardo Subercaseaux (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-16535.txt.
Description
Keerthana Gurushankar, Noah Singer, and Bernardo Subercaseaux prove latency bounds for caching with delayed hits in this 2025 paper. Classic caching assumes a missed page arrives before the next request. Real systems like content delivery networks break that assumption. In the delayed hits model, retrieval takes measurable time while requests keep coming.
Two numbers describe the setting, the delay ratio and the cache size. The authors analyze Least Recently Used, the standard practical policy. They prove it is competitive within a factor tied to delay times cache size. That guarantee is the first tight one for this model. Matching lower bounds show the analysis cannot improve in general. Practice favorite LRU now has firm theory for delayed settings.
Catalog record
| CREATOR | Keerthana Gurushankar, Noah G. Singer, Bernardo Subercaseaux |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 45 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-16535