Abstract
Distributional paging asks for a polynomial-time eviction rule that competes with the optimal online policy OPT when requests come from a known stochastic source. Two algorithms proposed by Lund, Phillips, and Reingold [FOCS, 1994] are canonical. Their randomized dominating distribution algorithm, designed for Markov sources, draws the page to evict from any distribution over the cache obeying a family of pairwise linear inequalities; their deterministic median algorithm, designed for sources whose inter-arrival times are independent across pages, discards the cached page with the largest lower median of its conditional next-request time. The original guarantees were 4 and 5; Pabbaraju and Vakilian [ICALP 2025] recently sharpened them to 2 and 4.
We show that neither sharpened constant admits further improvement in its respective source model. For Markov paging, we give two complementary factor-2 lower-bound constructions, each with an explicit polynomial-time dominating selector. A directed-cycle family has ratio 2k/(k + 1), while a recurrent four-page family with cache size three has ratio 2 − 4ε/3.
Our second shows that the median algorithm fails to be c-competitive whenever c < 4 in the independent inter-arrival model. These are separate results for distinct stochastic models. Since each lower bound matches the corresponding upper bound, the two competitive ratios are 2 and 4 in their respective settings. The strongest bounds previously were 1.5907 and 1.511.
The two lower bounds use different mechanisms. For the dominating distribution algorithm, the directed cycle exposes the half-mass mechanism in its cleanest form: half of the eviction mass is forced onto the page returning last, while a bad selector places the remaining half on the page returning first. The four-page construction turns the same extreme-point choice into a recurrent cascade across two slowly switching blocks. For the median algorithm, we build independent renewal processes that repeatedly mislead the median rule: the page with the latest median is nevertheless likely to be requested early, forcing a cascade of bad evictions, while a simple online policy can be made to pay arbitrarily close to one quarter as much.