Tight Latency Guarantees for Weighted Caching with Delayed Hits

Abstract

Driven by the massive parallelism of modern multicore architectures and high-bandwidth networks, system throughput has increasingly outpaced physical latency limits. In such high-throughput environments, the ratio Z between retrieval latency and the request inter-arrival time becomes a dominant performance factor. We study the paging with delayed hits problem, a framework that captures these dynamics in systems such as CDNs and MEC. In this model, each page load incurs a delay of Z time steps, during which requests for the same page can be batched and served together, with costs proportional to both request weight and waiting time. Our primary contribution is a black-box reduction that transforms classical paging algorithms into their delay-aware counterparts. We prove that any β-competitive classical paging algorithm can be transformed into an O(Zβ)-competitive algorithm for delayed hits in both deterministic and randomized settings. Applying this reduction to known randomized algorithms yields an O(Z log k)-competitive policy, which we show is asymptotically optimal via a matching Ω(Z log k) lower bound. Technically, our results rely on a structural theorem showing that classical paging solutions can be transferred between suitably related request sequences with only a bounded multiplicative loss in cost. This theorem isolates a fundamental property of paging that may extend to a broader class of online problems with service delays. Altogether, our results provide a framework for designing delay-aware algorithms via classical paging algorithms, yielding new optimal bounds in high-latency, parallel environments.