Paging with Per-Replacement Maximum Delay

Abstract

Classical paging couples every miss to an immediate replacement. We ask what remains of its algorithmic structure when a miss may wait. In our per-replacement maximum-delay model, loading a pending page costs one unit of movement plus the age of its oldest outstanding request and clears the whole page-specific episode. Equivalently, the instantaneous holding rate is the number of pending pages, rather than the number of pending requests. The classical competitive hierarchy survives this change. For cache size $k$, we give a deterministic $(5k+3)$-competitive threshold-LRU algorithm and a randomized $5H_k$-competitive algorithm against an oblivious adversary; classical lower-bound instances give matching $\Omega (k)$ and $\Omega (H_k)$ orders. The randomized algorithm uses cache-independent temporal windows to create an ordinary-paging sequence fixed before any random choices; a shadow paging algorithm is then projected onto nonproactive physical replacements. The offline picture is less classical. We give an exact $O(nk)$ dynamic program with one hole, an exact configuration dynamic program for a fixed number of holes, and a deterministic nonproactive polynomial-time $5$-approximation without fixing that number. Yet farthest-next-use victim selection can be suboptimal in the physical delayed problem already with three pages.