PaperlayerView exact revision on arXiv

Source-linked AI summary

Paging with Per-Replacement Maximum Delay

Tianhang Lu, Runtian Ren, Shengcai Liu

arXiv:2608.25290v1cs.DS

TL;DR

The paper asks what remains of paging when a miss may wait, with delay charged per pending page episode rather than per request. It develops temporal aggregation, shadow-cache projection, and exact or approximate offline methods. The classical online hierarchy survives under unit costs, but physical farthest-next-use can fail and unequal fetch costs introduce spread-dependent limits.

  • Problem

    The paper asks which classical paging guarantees and structural properties survive when misses may wait and service timing becomes an algorithmic decision.

  • Method

    The paper combines cache-independent temporal windows, shadow paging projected onto nonproactive replacements, causal laziness, and dynamic programming for restricted offline states.

  • Results

    Under unit fetch costs, deterministic and randomized online orders remain Θ(k) and Θ(Hk), while offline methods include exact restricted-hole algorithms and a deterministic polynomial-time 5-approximation.

  • Takeaways & Limitations

    Classical paging rules remain useful after timing is handled separately, but Belady’s farthest-next-use rule is valid only in the virtual paging instance, not necessarily physically.

  • Takeaways & Limitations

    The unrestricted-hole exact complexity remains unresolved, and the general-metric extension requires new ideas to remove aspect-ratio dependence and shared-delay complications.

Abstract

from arXiv · show

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 $Ω(k)$ and $Ω(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.

1 Introduction

The paper studies paging when missed pages may wait before replacement, separating timing decisions from eviction decisions. It shows that much of paging’s online hierarchy and algorithmic structure survives, while offline optimality and unequal fetch costs expose new boundaries.

  • Problem and model: Waiting introduces a timing decision in addition to choosing which cached page to evict.An eviction also determines which future request becomes pending.
  • Main conclusions: Maximum delay preserves the classical competitive hierarchy more robustly than classical offline optimality under unit fetch costs.The paper develops deterministic and randomized online guarantees alongside exact and approximate offline algorithms.
  • Offline structure: The offline problem has an exact one-hole dynamic program, an exact fixed-hole configuration dynamic program, and a polynomial-time deterministic 5-approximation for unrestricted holes.Physical farthest-next-use can nevertheless be suboptimal with three pages.
  • Weighted extension: Unequal fetch costs introduce spread-dependent guarantees and a timing barrier already with one cache slot.The weighted extension uses ρ = wmax/wmin and includes a strict Ω(√ρ) randomized lower bound.
  • Scope and limitations: The general-metric extension remains outside the main development because removing aspect-ratio dependence and sharing one maximum-delay charge across moves require new ideas.This is identified as a scope boundary rather than a resolved result.
  • Techniques: Input-only temporal windows create a request sequence fixed before random choices, while shadow paging is projected onto nonproactive physical replacements.This architecture supports the randomized online bounds and the offline approximation.

2 Model and Structural Preliminaries

The model represents delayed service through page-level pending episodes and a holding rate based on pending holes. Structural normal forms and causal laziness simplify schedules without increasing cost, supporting dynamic programming and nonproactive algorithms.

  • Model: A cache has k resident pages, with the complementary pages represented as holes; the initial cache is fixed and shared with the comparator.The final cache configuration is unrestricted.
  • Model: A miss starts a page-specific pending episode, and later requests to that missing page join it without resetting its start time.Requests to cached pages are satisfied immediately.
  • Cost: Loading a pending hole clears its episode and costs movement plus the episode’s age, whereas proactive loading costs movement only.The total objective is replacements plus page-episode delay.
  • Holding representation: The holding representation charges the number of pending holes over time, so repeated requests to one page do not increase the holding rate.An event-layer dynamic program therefore charges future gaps using |B|∆.
  • Structural normal form: Every feasible schedule can be normalized so actions occur at post-batch cuts without increasing cost or changing caches seen by arrivals.The complete ordered action word in each inter-arrival layer moves to its left post-batch cut.
  • Causal laziness: Causal lazy projection converts any schedule into a nonproactive schedule with no greater cost under uniform movement and free terminal cache.The construction is causal and uses no future input.

3 Offline Structure and Algorithms

The offline analysis exploits causal laziness to obtain an exact O(nk) dynamic program with one hole and an exact configuration dynamic program for fixed holes. However, physical farthest-next-use is not optimal, so unrestricted configurations must retain the current hole set.

  • One-hole optimization: The one-hole state is the hole identity plus a pending bit, because the same hole can be either pending or clean.Waiting is allowed, and loading a pending hole costs one movement plus its waiting time.
  • One-hole optimization: O(nk) time computes the exact offline optimum when the cache has one hole.The dynamic program uses 2(k + 1) states per arrival epoch and O(k) working space.
  • Physical farthest-next-use can fail: Farthest-next-use is suboptimal physically: with k = 2 and pages {p, q, f}, the unrestricted optimum costs 5/2 while every such schedule costs at least 3.At time zero, farthest-next-use uniquely evicts f, whereas the optimum evicts q and later reloads it after a half-unit delay.
  • Configuration dynamic program: Because future request times do not determine the best physical victim, the exact general-hole state retains the full hole set and its pending subset.Lazy service replaces a pending page with a cached victim, updates H and B, and yields an acyclic same-epoch closure.
  • Configuration dynamic program: The exact fixed-hole configuration dynamic program has states for hole sets and pending subsets, with each state having at most rk service edges.The recurrence is exact, with state and running-time bounds stated by Theorem 3.4.
  • Configuration dynamic program: For fixed r, the configuration algorithm is XP rather than FPT, while the unrestricted-hole exact complexity remains unresolved.The state growth is controlled by requested pages, but no polynomial or FPT algorithm is established for arbitrary r.

4 Deterministic Online Algorithms for a General Page Universe

Threshold-LRU services pending pages after fixed delays, using recency rules and explicit event ordering. Phase charging bounds its deterministic cost by offline movement and holding, yielding a (5k+3)-competitive algorithm with a matching Ω(k) lower-bound order.

  • Algorithm: Each page starts a timer at its oldest request and is loaded θ later, clearing its pending episode.Arrival batches update recency before deadline actions, and deadline ties use a fixed page order.
  • Algorithm: Arrival-LRU retains actual-arrival keys, whereas Service-touch LRU overwrites a loaded page’s key using service micro-order.Both variants explicitly order simultaneous arrivals and services, and a newly loaded page may be evicted at the same timestamp.
  • Analysis: At most k activation-hit timers touch each offline movement, while quarantine and purge isolate at most 4k exceptional contained timers per noninitial phase.After the purge, every online-cache outsider is offline-pending, enabling timer-length charging to offline holding.
  • Analysis: Post-purge regular timer lengths integrate to the offline holding cost, while activation misses and crossing hits are charged to offline holding or movement.The unified bound applies to either recency rule and every feasible lazy offline comparator.
  • Guarantees: Choosing θ = 2/(5k + 1) gives ALG ≤ (5k + 3) OPT.Every service costs at most 1 + θ, and the deterministic lower-bound construction has ratio k(1 + θ) = Ω(k).
  • Guarantees: For k = r = 2, Arrival-LRU pays six, Service-touch LRU pays four, and OPT pays two on a specified tied-batch instance.Service-touch protects page 0 while Arrival-LRU immediately re-evicts it.

5 Temporal Aggregation for a General Page Universe

Temporal aggregation separates the raw input from cache and random choices, then projects shadow paging decisions onto pending-only physical replacements. Exact virtual paging yields a deterministic 5-approximation, while classical randomized paging yields a 10Hk bound at θ = 2/3.

  • Reduction: Temporal aggregation produces a virtual sequence determined only by the raw input and θ, independent of cache states and random choices.This removes the adaptive-sequence problem that arises when delayed service streams depend on earlier random evictions.
  • Reduction: AW-A(θ) runs a lazy classical paging algorithm in a shadow cache and physically replaces pages only when the corresponding page is pending.Raw hits do not update the shadow cache, and a shadow fault without a physical pending page causes no physical action.
  • Projection: Pathwise, the number of physical replacements G is at most the number of shadow faults F, and ALG ≤ (1 + θ)F.Every physical replacement is nonproactive.
  • Deterministic offline use: Using exact classical paging in the shadow cache gives a deterministic nonproactive polynomial-time 5-approximation.At θ = 2/3, the delayed optimum’s virtual fault count satisfies F* ≤ 3 OPT, leading to ALGoff ≤ 5 OPT.
  • Deterministic offline use: Within this framework, θ = 2/3 is optimal for balancing delay and movement coefficients, so improving five requires strengthening another proof component.Changing only the window length cannot improve the factor.
  • Randomized online use: At θ = 2/3, AW-Marker satisfies E[ALG] ≤ 10Hk OPT against an oblivious adversary, and every randomized online algorithm has competitive ratio Ω(Hk).The lower bound already holds on a universe of k + 1 pages.
  • Randomized online use: Direct multi-hole service phases fail because a common deadline can create k deterministic services, whereas virtual phases avoid this through harmonic accounting and a pre-randomness-fixed sequence.This explains why the aggregation construction uses virtual rather than raw service phases.

6 Weighted Fetch Costs

Weighted fetch costs preserve the paper’s structural and fixed-hole results, but arbitrary weight spread makes approximation and competitiveness spread-dependent. A temporal reduction yields polynomial offline and online guarantees, while a one-slot lower bound shows strict spread dependence is necessary.

  • Structural preservation: Weighted causal laziness and the exact one-hole and fixed-r algorithms retain their unit-cost running times.Proactive loading cannot improve the weighted offline optimum or a competitive guarantee against an oblivious input.
  • Exact algorithms: Exact weighted offline computation remains O(nk) with one hole and polynomial-time for every fixed number of holes.The fixed-hole configuration dynamic program retains the unit-cost running-time structure.
  • Temporal reduction: Input-determined page-dependent windows create a virtual weighted-paging sequence before cache choices or random bits, then shadow paging is projected onto nonproactive physical replacements.The projection compares physical and shadow movement through a discrepancy potential and bounds page-episode cost by (1 + θ)wp.
  • Weighted guarantees: (3ρ + 2) offline approximation, O(ρk) deterministic online competitiveness, and O(ρ log k) randomized competitiveness hold for arbitrary page sets.The randomized guarantee is against an oblivious adversary.
  • Spread dependence: When ρ = 1, the offline coefficient is five, while arbitrary spread introduces a strict randomized lower bound already with one cache slot.The lower-bound construction uses two pages and shows no strict multiplicative ratio depending only on k over arbitrary weights.

7 Discussion: Survival and Failure

Under unit costs, delayed paging preserves classical online orders and supports temporal reductions, but physical offline victim selection changes. Unequal costs make timing spread-sensitive, leaving exact complexity and several algorithmic gaps open.

  • What survives: Unit-cost deterministic and randomized online orders remain Θ(k) and Θ(Hk), with LRU and Marker useful after distinct timing and aggregation mechanisms are added.The randomized timing layer uses input-only windows and a shadow cache.
  • What changes: Farthest-next-use can be suboptimal for the physical delayed optimum with three pages, although Belady remains exact in the virtual ordinary-paging instance.The unrestricted exact offline complexity remains unresolved.
  • What changes: The physical offline state retains both a hole configuration and a pending subset beyond the one-hole case.Waiting couples service time, the loaded pending page, and the evicted victim.
  • Unequal fetch costs: The Ω(√ρ) lower bound with two pages and one cache slot shows that unequal fetch costs make online timing spread-sensitive.Serving a cheap pending page may displace an expensive resident page before its next request.
  • Open questions: The exact unrestricted-hole complexity, improved approximation factors, the online weight-spread gap, and a paging-native alternative to shadow caches remain open.The paper explicitly lists these as future questions.

A Online Algorithms with One Hole

For m = k + 1, the unique-hole setting limits pending episodes and makes busy intervals of a fixed-threshold algorithm disjoint.

  • One-hole setting: The one-hole case assumes m = k + 1, so the unique hole can have at most one pending page episode.This makes the busy intervals of a fixed-threshold algorithm strictly disjoint.

A.1 Deterministic threshold LRU

Threshold-LRU waits a fixed threshold after the hole is requested, then loads it while evicting the least recently requested cached page. Its threshold choice yields a strict multiplicative bound.

  • Rule: At the deadline, threshold-LRU processes the complete batch before replacing the evicted page.The algorithm waits exactly θ after the hole is first requested.
  • Notation: The one-hole theorem measures movement cost, delay cost, and online services against a lazy offline optimum.The theorem denotes these quantities by M, D, and N, respectively.
  • Guarantee: θ = 1/(k + 2) gives threshold-LRU a strict multiplicative (k + 3) bound.The bound follows from charging covered busy intervals to OPT delay and movement, with at most k uncovered services per noninitial idle component.

A.2 Randomized service-anchored Marker

The service-anchored randomized Marker rule avoids failures of arrival-defined phases and achieves a harmonic expected-service bound against oblivious adversaries. A pathwise reset bound converts this into the stated competitive guarantee, while the proof depends essentially on obliviousness.

  • Randomized service-anchored Marker: The service-anchored rule serves a pending hole at age one, evicts uniformly among unmarked pages when possible, and resets marks otherwise.Initially all cached pages are marked; after a reset, only the loaded page remains marked and the new hole is clean and unmarked.
  • Randomized service-anchored Marker: R ≤ 3 OPT completed reset-to-reset blocks pathwise because one-hole service intervals have overlap at most three.Consecutive services are separated by strictly more than one time unit under the arrival-first convention.
  • Randomized service-anchored Marker: The expected service count is at most 1 + H_k(3 OPT + 1), and threshold-one services cost exactly two.The first online service is a reset, while each completed or terminal block contributes at most H_k expected services.
  • Limitations: The proof requires an oblivious adversary because an adaptive adversary could request the randomly selected victim next.The general-hole dynamic program is exponential when the effective number of holes is unfixed, whereas a polynomial-time 5-approximation is available.

B.2 Certified nonintegrality

The marginal LP is provably nonintegral, with a certified 8/7 integrality gap on a four-page instance. The construction also shows why exact marginal-preserving slotwise rounding fails, leaving approximation and LP-gap questions separate.

  • Certified gap: The marginal LP has an integrality gap of at least 8/7.This is certified by a four-page, cache-size-one instance with integral OPT equal to four and fractional cost approaching 7/2.
  • Certified gap: The gap instance uses initial cache {d} and batches {a, d}@0, {c}@ε, and {b, d}@1 + ε.Its fractional actions are 1/2(b → c), 1/2(d → b), and 1/2(b → d).
  • Marginal trajectory: Table 3 tracks a marginal trajectory whose rows each have total hole mass three and per-page mass at most one.Formal sums such as b+c+1/2d encode clean-hole mass on b and c and one-half unit on d.
  • Rounding limitation: Slotwise rounding cannot preserve the exact clean-hole and pending-hole marginals in general.A two-realization example makes clearing one pending page force the clearing of another pending page in the alternate realization.
  • Open questions: The 5-approximation does not establish an LP integrality-gap upper bound, so improving the factor and determining the full gap remain separate questions.No inequality of the form ALGoff ≤ 5 LP has been proved; the certified 8/7 lower bound remains compatible with either a constant or unbounded gap.

C A First General-Metric Transfer

The general-metric extension tests how far the temporal reduction reaches beyond the uniform metric. It yields an aspect-ratio-dependent black-box theorem for endpoint-batch requests, not a solution for arbitrary-metric delayed k-server.

  • C A First General-Metric Transfer: The extension obtains an aspect-ratio-dependent black-box theorem for the direct endpoint-batch model.The result is explicitly not presented as a solution to delayed k-server on arbitrary metrics.

C.1 Endpoint-batch model

The endpoint-batch model extends delayed paging to finite metrics by charging distance plus oldest-request delay for pending episodes. A lazy classical k-server algorithm transfers causally to a nonproactive delayed algorithm, with the randomized case requiring oblivious input timing.

  • Model: An unoccupied request point starts one pending episode, and moving a server to it costs distance plus the oldest arrival’s age.Requests to an occupied point are served immediately; moves to nonpending points are proactive and pay only distance.
  • Model: On a uniform metric, nonproactive trajectories preserve distinct server locations and coincide with paging trajectories.This recovers the paging specialization of the delayed model.
  • Transfer theorem: A lazy classical k-server algorithm satisfying a classical competitive guarantee yields a causal nonproactive algorithm for endpoint-batch delays.The configuration distance is defined by minimum perfect matching between server copies.
  • Transfer theorem: Randomized transfer requires the raw timed input to be fixed by an oblivious adversary.The same restriction prevents the adversary from adapting timing to random choices.
  • Guarantee: When X is uniform, Γ_X = 1 and the temporal coefficient is exactly five.The strict classical work-function guarantee gives a strict O(kΓ_X) ratio with an additive constant.

C.2 Input-only windows and matching projection

Input-only temporal windows convert the timed request stream into a virtual classical sequence fixed before server choices, while matching projects shadow movements onto nonproactive physical repairs. The resulting analysis bounds physical movement and delay through window length and bad-representative charges.

  • Input-only windows: The virtual sequence is determined by timed arrivals and window deadlines before any server choices or random bits.Each window emits one virtual request when it closes; arrivals through the endpoint join that window.
  • Matching projection: Shadow paging processes the virtual sequence, and physical service moves a server matched to the requested shadow copy only when that page is pending.When the page is not pending, the physical configuration takes no action.
  • Matching projection: Every physical movement is nonproactive, and total physical movement is at most shadow movement, G ≤ F.The minimum-matching potential decreases by at least each physical repair length and is initially zero with nonnegative terminal value.
  • Matching projection: A physical episode created in an x-window remains pending until its representative and has age at most L, yielding delay at most θg for repair length g.Because pending x is unoccupied, each repair has positive length at least δX.
  • Comparator analysis: Bad representatives are charged either to full-window holding cost or to a departure movement, bounding their number using D/(θδX) and M/δX.Successive windows for one point have disjoint interiors, and each movement is charged at most once.
  • Comparator analysis: The virtual k-server comparator is made lazy through minimum-matching distance, so the classical guarantee applies directly to the input-only virtual sequence.The proof couples proactive movements of the comparator to a lazy classical configuration and removes proactive cost by telescoping the potential.

C.4 Why the aspect ratio remains

The single-scale temporal reduction has aspect-ratio dependence because long windows hurt nearby requests while short windows induce repeated long crossings. This limitation does not rule out better delayed algorithms, and shared-event service requires a separate model.

  • Single-scale limitation: The proved dependence on ΓX is a limitation of the single-scale transfer, not a lower bound for every delayed algorithm.The paper uses a three-point construction to show that one common window length cannot yield an aspect-independent shadow reduction.
  • Single-scale limitation: A long window is expensive for a nearby request, whereas a short window forces repeated long crossings; balancing these losses leaves at least ∆/δ.The two inputs respectively produce ratios at least 1 + τ/δ and asymptotically ∆/τ.
  • Assignment limitation: A purely local nearest-server trigger can cross the same edge forever, while moving a different server once lets the offline solution hit every subsequent request.The example shows why persistent credit and geometry-aware server assignment matter even at constant aspect ratio.
  • Open direction: A proposed multi-scale direction retains server–subtree commitments, but a direct component-to-server matching can already fail for k = 2.The missing ingredient is a multi-root certificate.
  • Model boundary: The shared-event model, where multiple servers may serve several request points under one maximum delay, is separate because a request corresponds to a service set rather than one configuration.The preceding request identity no longer determines the next spatial anchor, so Theorem C.1 does not apply.
Loading 2608.25290v1…