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

CREATORKeerthana Gurushankar, Noah G. Singer, Bernardo Subercaseaux
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE45 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-16535

Browse the full library · About the Tower of Babel