Allowing a cache miss to wait does not erase the paper's online guarantees for paging, but it changes the offline problem enough to break a familiar replacement rule. In a cache-size-two example, the unrestricted optimum costs 5/2, while every schedule that physically evicts the page with the farthest next use costs at least 3.
The paper studies paging when a cache miss can remain pending under a per-replacement maximum-delay objective. Its formal input is a finite page set, with cache configurations represented by subsets containing k pages, where k is the cache size. The question is therefore about algorithmic guarantees and computational structure.
Counting the wait
One subtle choice shapes the model. A pending episode is charged separately for each missing page, not for every repeated request. Once a page is missing, more requests for that same page do not increase its holding rate. Other missing pages remain separate obligations.
In the uniform-cost version, and when the final cache configuration is free, any feasible schedule can be transformed into a causal nonproactive one without increasing either movement or delay. Under those assumptions, the analysis does not need replacements made before a request demands them.
The exact frontier
The sharpest exact result is for the one-hole case. The offline optimum can be found by a dynamic program that keeps two times one more than the cache size states at each arrival epoch, uses working space proportional to cache size, and runs in time proportional to the number of arrival epochs multiplied by cache size.
For a fixed number of holes, the paper places the exact configuration algorithm in the XP class, so its tractability is tied to holding that number fixed. Once the number of holes is unrestricted, the exact complexity is unresolved. The paper does provide a deterministic, nonproactive polynomial-time five-approximation to the offline optimum.
Online policies keep their footing
Threshold-LRU has a strict competitive factor of five times the cache size plus three when its timer threshold is set to two divided by five times the cache size plus one. The paper also proves that every deterministic online algorithm has a lower-bound order that grows proportionally to cache size.
The randomized result follows a different route. Temporal aggregation creates a virtual request sequence from the raw input and the timing parameter alone, independently of cache state and random choices. AW-Partition, with parameter 2/3, has an expected cost no more than five times the paper's harmonic term multiplied by the offline comparator against an oblivious adversary. A lower bound on a universe of k+1 pages gives every randomized online algorithm a competitive ratio of at least the same harmonic order.
Weights change the picture
The picture becomes less tidy when fetching different pages has different costs. The exact fixed-hole algorithms and structural results survive without loss under page-dependent fetch costs. If the weight spread is the ratio of the most expensive fetch to the cheapest, the reported guarantees become a deterministic offline approximation of three times that spread plus two, a deterministic online factor proportional to spread times cache size, and a randomized factor proportional to spread times the paper's harmonic term against an oblivious adversary.
For one cache slot and a weight spread of at least 2, the randomized lower bound grows with the square root of the spread. In particular, it is at least the square root of the spread divided by four. The result rules out a strict competitive ratio that depends only on cache size for arbitrary positive page costs.
What the results leave open
A related marginal linear program has an integrality gap of at least eight-sevenths. More broadly, the exact complexity with an unrestricted number of holes remains unresolved, and the randomized guarantees are stated against an oblivious adversary.
The manuscript is an arXiv preprint, version 2 dated 11 Sep 2026. Its claims concern the formal page-and-cache model, so they describe algorithmic bounds rather than measured performance in a deployed system.
Paper data and sources
Original title: Paging with Per-Replacement Maximum Delay
Authors: Tianhang Lu, Runtian Ren, Shengcai Liu
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-26
DOI: Not available
Original paper · Full text