PaperlayerView exact revision on arXiv

Source-linked AI summary

Two Holes Make a Difference: Deterministic Paging with Delay and Deadlines

Darya Melnyk, Linda Thelen, Yuyi Wang

arXiv:2610.18767v1cs.DS

TL;DR

Paging with delay lets requests wait at a delay cost, but the claimed 2k+1 competitive bound does not hold in general. The paper analyzes threshold-FIFO and deadline-triggered algorithms, establishing bounds that depend on the number of holes. It also proves a deterministic deadline lower bound and derives a lower bound for threshold algorithms with delay.

  • Problem

    The claimed 2k+1 upper bound for paging with delay may hold only with one hole, leaving the general competitive ratio unresolved.

    Source: §1 · p. 1

  • Method

    The paper analyzes threshold-triggered paging algorithms with FIFO replacement for delay and deadlines, and proves a deterministic lower bound for deadlines.

    Source: §1 · p. 2, §5 · p. 10

  • Results

    Strictly (2k + 2)-competitive: δ-FIFO for delay; for deadlines, the upper bounds are k + 1 generally and k with one hole, while the deterministic lower bound is k + 1/2 on k + 2 or more pages.

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    With one hole, the deadline bound matches classical paging, but more than one hole makes deadlines strictly harder; every deadline lower bound ρ also yields a threshold-delay lower bound of ρ+k+1.

    Source: §1 · p. 2

    For paging with delay on at least k + 2 pages, the optimal deterministic ratio remains between 2k + 1 and 2k + 2, and attaining 2k + 1 would require an algorithm outside the fixed-threshold class.

    Source: §7 · pp. 16–17

Abstract

from arXiv · show

In this paper, we study online paging with delay or deadlines. In online paging with delay, an online algorithm manages a cache of size $k$ and needs to serve incoming requests by adding the requested pages to the cache. In addition, it has the option to delay serving incoming requests at a cost that depends on the delay. We propose a new online algorithm, which combines a threshold rule with first-in, first-out (FIFO) replacement, and show that it is $(2k+2)$-competitive for cache size $k$. This result corrects a previously published claim that the competitive ratio is exactly $2k+1$ regardless of the number of holes (pages outside the cache). However, in the case of one hole, we show that the FIFO rule with a different threshold is indeed $(2k+1)$-competitive, giving a tight result. In the case of deadlines, the same analysis gives a deadline-triggered algorithm that is $(k+1)$-competitive in general and $k$-competitive if there is only one hole. Moreover, we show that the second hole makes paging with deadlines strictly harder than classical paging, where the competitive ratio is independent of the number of holes. For paging with deadlines, we prove a deterministic lower bound of $k+\tfrac12$, already for two holes. We show that, as a consequence, no threshold-triggered algorithm can achieve a competitive ratio less than $2k+\frac32$ in general.

1 Introduction

The paper corrects the claimed general 2k+1 bound for paging with delay and gives threshold-FIFO bounds for delay and deadlines. It also shows that deadlines become strictly harder than classical paging when there is more than one hole.

1 Introduction

  • Paging maintains k pages from a universe of n > k; a request outside the cache requires loading that page and evicting another.The problem is a foundational online-computation problem and has motivated weighted and learning-augmented variants, as well as broader models.Source: §1 · p. 1
  • The LRU rule from exceeds 2k + 1 on the illustrated sequence: for k = 2, its cost is 12.5 versus Opt's 2, a ratio of 6.25.The sequence can be continued by swapping the outer and inner pages and repeating the requests.Source: §1 · p. 2, Figure 1 · p. 2
  • Strictly (2k + 2)-competitive: δ-FIFO fetches when accumulated delay reaches a fixed threshold and evicts in FIFO order.The algorithm is nonclairvoyant.Source: §1 · p. 2
  • On k + 1 pages, FIFO with threshold k+1 is strictly (2k+1)-competitive, while fixed-threshold FIFO is no better than (2k + 2)-competitive on k + 2 or more pages.This recovers the claimed bound from for one hole; the analysis is tight for fixed-threshold FIFO.Source: §1 · p. 2
  • For paging with deadlines, the upper bound is k + 1 in general and tight k with one hole; more than one hole makes it strictly harder than classical paging.Classical paging's competitive ratio does not depend on the number of holes.Source: §1 · p. 2
  • At least k + 2 pages give every deterministic clairvoyant deadline algorithm a competitive ratio lower bound of k + 1/2.The construction uses k + 2 pages and extends to more pages.Source: §1 · p. 3
  • For threshold algorithms with delay, every deadline lower bound ρ yields a lower bound of ρ+k+1; threshold-triggered FIFO upper bounds are exactly k + 1 above the deadline upper bounds.The paper studies algorithms that time fetches using a fixed delay-cost threshold.Source: §1 · p. 3

2 Model and notation

The model specifies request timing and delay costs, cache updates, and the distinction between online, nonclairvoyant, and offline algorithms. It also defines threshold-triggered fetches and the deadline variant.

2 Model and notation

  • Each delay-paging request specifies a page, arrival time, and continuous, nondecreasing, unbounded delay-cost function that is zero at arrival.A request is served the first time after arrival that its page enters the cache.Source: §2 · p. 4
  • Online actions depend on requests received so far; nonclairvoyant actions also cannot depend on future delay-cost curves, while offline algorithms know the full sequence.An algorithm is ρ-competitive when its cost is at most ρ times Opt plus a sequence-independent constant; it is strictly competitive when that constant is zero.Source: §2 · p. 4
  • A cache holds up to k pages; a miss costs one fetch, eviction is free, and serving a request incurs its delay cost.The online and offline algorithms start with the same cache of size k; pages outside a full cache are called holes.Source: §2 · p. 4
  • A fixed-threshold algorithm fetches an uncached page when its accumulated delay first reaches δ, serves its pending requests, and applies its replacement rule.A threshold-triggered fetch and the service of its pending requests together form a payment.Source: §2 · pp. 4–5
  • In paging with deadlines, requests must be served by their deadlines and incur no delay cost beforehand, so total cost is the number of fetches.This variant can be modeled as delay paging with costs that jump to a very large value immediately after each deadline.Source: §2 · p. 5

3 FIFO upper bounds for paging with delay

The section analyzes δ-FIFO, which fetches a page after its accumulated delay reaches a threshold and uses FIFO replacement. Payment-window accounting with a rank potential yields a (2k + 2) guarantee generally and (2k + 1) when there is one hole.

3.1 The δ-FIFO algorithm

  • δ-FIFO fetches a page when its accumulated delay reaches δ and evicts the page fetched earliest; each payment costs 1 + δ.A cache hit leaves the FIFO order unchanged, and the algorithm is nonclairvoyant for every δ > 0.Source: §3.1 · p. 5

3.2 Upper bounds for the competitive ratio of FIFO

  • The proof divides time into payment windows and uses a queue-rank potential to account for online payments and offline fetches.A page’s windows are disjoint, while windows for different pages may overlap when there are more than k + 1 pages.Source: §3.2 · pp. 5–6
  • On k + 1 pages, an offline eviction of a page outside the online cache decreases the potential by at least 1; with more pages, that decrease is not guaranteed.At an online payment, the potential decreases by at least 1 if the requested page is in Opt’s cache, and otherwise increases by at most k.Source: §3.2 · pp. 6–7
  • The payment accounting charges each online payment against offline fetches, offline delay, and potential changes across three cases.The cases depend on whether Opt has the requested page at payment time, had it earlier in the window, or never cached it during the window.Source: §3.2 · pp. 7–8
  • (2k + 2)-competitive: 1-FIFO achieves this strict bound for paging with delay in the general case.The analysis chooses threshold δ = 1.Source: §3.2 · p. 9
  • (2k + 1)-competitive: with one hole, k-FIFO achieves this strict bound.The threshold is δ = (k + 1)/k.Source: §3.2 · p. 9

4 FIFO upper bounds for paging with deadlines

The section analyzes deadline-triggered FIFO, which fetches a page when a pending request reaches its deadline and serves the page’s other pending requests at that time. Its competitive guarantee is k + 1 generally and k with one hole, while the deterministic ratio with at least two holes lies between k + 1/2 and k + 1.

4 FIFO upper bounds for paging with deadlines

  • A fetch at a request’s deadline serves every other pending request for that page, and the algorithm’s cost is its number of payments.The deadline model’s payment windows and rank potential carry over from the delay analysis, while feasible offline schedules must cache each paid-for page during its window.Source: §4 · p. 9
  • With one hole, deadline-triggered FIFO is strictly k-competitive, and no deterministic online algorithm can do better.This matches the lower bound from classical paging.Source: §4 · p. 10
  • Deadline-triggered FIFO is strictly (k + 1)-competitive on n ≥ k + 1 pages.The deadline accounting uses the payment-window and rank-potential analysis; deadlines rule out the third case in the delay analysis.Source: §4 · pp. 9–10
  • Together with Theorem 1.3, the deterministic competitive ratio for paging with deadlines on n ≥ k + 2 pages lies in [k + 1/2, k + 1].Source: §4 · p. 10

5 A deterministic lower bound for paging with deadlines

The section proves a deterministic lower bound of k + 1/2 for paging with deadlines on at least k + 2 pages. Its adversarial construction tracks offline schedules through phases, keeping offline cost bounded while forcing online misses.

5 A deterministic lower bound for paging with deadlines

  • k + 1/2 is a lower bound on the competitive ratio of every deterministic clairvoyant deadline-paging algorithm when n ≥ k + 2.The construction uses k + 2 pages and extends to larger universes.Source: §5 · p. 10

5.1 The offline choices and the adversary

  • The adversary requests pages absent from the online cache and divides the sequence into phases as its offline budget increases.Each request raises online cost by at least one, while offline cost rises by at most one per phase.Source: §5.1 · p. 10, §5 · p. 10
  • A cheap offline schedule stays within budget B, serves expired requests, and ends with holes at the held page h and another page z.The construction maintains schedules costing at most B or B + 1, with a served-held-request guarantee for unstarred candidates.Source: §5.1 · p. 11
  • The phase adversary continues by removing candidates from C, then starts a new phase when no continuation is possible.A phase starts with k candidates or k + 1 candidates, depending on whether the new page was previously starred.Source: §5.1 · pp. 11–12

5.2 Cost analysis

  • The construction ensures every request is a miss and requires a separate online move, so Alg incurs cost at least N on σN.The request windows at any one page do not overlap.Source: §5.2 · p. 13
  • The phase accounting bounds offline cost while the online cost grows with N, establishing the lower bound despite an additive competitive constant.The analysis counts completed short and long phases, which contain at least k and k + 1 requests, respectively.Source: §5.2 · p. 13

6 Lower bounds for threshold algorithms

This section establishes lower bounds for threshold algorithms in paging with delay. It proves fixed-threshold FIFO tightness and transfers deadline lower bounds to show that no threshold algorithm achieves a ratio below 2k + 3/2 on at least k + 2 pages.

6.1 Tightness for fixed-threshold FIFO

  • 2k + 2 is a lower bound for δ-FIFO at every fixed threshold δ > 0 when n ≥ k + 2.The repeatable adversarial run makes FIFO pay (1 + δ)(2k + 2), while the offline witness pays at most 1 + δ per run.Source: §6.1 · pp. 13–14, Figure 4 · p. 14
  • The adversarial sequence uses k + 2 pages and orders critical requests so FIFO faults on every request.The endpoints of each run match up to renaming b and c, allowing the run to repeat.Source: §6.1 · p. 14

6.2 Transferring deadline lower bounds

  • The deadline-to-delay transfer yields a deterministic deadline algorithm with competitive ratio at most ρ/(1 + δ) from a ρ-competitive threshold algorithm.The simulated deadline algorithm copies fetches and evictions; the construction uses virtual time and deadlines assigned to delay requests.Source: §6.2 · pp. 15–16
  • A deadline lower bound ρ implies that threshold algorithms for delay cannot have ratio below ρ + k + 1 on the same universe.The proposition applies for k ≥ 1 and n ≥ k + 1.Source: §6.2 · p. 16

6 Lower bounds for threshold algorithms

  • For online paging with delay on at least k + 2 pages, Theorem 6.4 states that no threshold algorithm has competitive ratio less than 2k + 3/2.Source: §6.2 · p. 16

6.2 Transferring deadline lower bounds

  • Theorem 6.4 states that, for online paging with delay on at least k + 2 pages, no threshold algorithm has competitive ratio below 2k + 3/2.Source: §6.2 · p. 16

7 Discussion and future work

The paper leaves open the optimal deterministic competitive ratio for paging with delay, while showing that deadline bounds clarify but do not resolve that gap. It also identifies randomized algorithms against an oblivious adversary as future work.

7 Discussion and future work

  • For paging with delay on at least k+2 pages, the optimal deterministic ratio remains open between lower bound 2k+1 and upper bound 2k+2.The upper bound is tight for fixed-threshold algorithms, but may not be optimal among all online algorithms.Source: §7 · p. 16
  • Achieving 2k+1, if possible, requires an algorithm outside the fixed-threshold class.Even for n=4 and k=2, the optimal deterministic ratio remains between 5 and 6.Source: §7 · pp. 16–17
  • Deadline bounds may help clarify the delay gap, but transferring deadline lower bounds to fixed-threshold algorithms does not resolve the unrestricted delay optimum.Proposition 6.3 gives the transfer an additive increase of k+1.Source: §7 · p. 17
  • Closing the deterministic competitive-ratio gaps and studying randomization against an oblivious adversary remain future work.Source: §7 · p. 17
Loading 2610.18767v1…