Infinite prefixes, real-speed banks and unbounded makespan ratios
DefinitionChangingCache_UpperBound_Supplement_StreamsFor an infinite request stream , let be its first requests. A single family of cache snapshots is legal on the stream if it is legal, in the published finite-cache model, on every prefix, with the same snapshots throughout.
For real speed , profile , and a designated policy , the bank is
The predicate for an unbounded makespan ratio means
Here is a positive growth-limited memory profile and is a nonempty finite list. LRU has memory factor two and the published capacity after misses. Natural page names permit arbitrarily many distinct pages. The ratio condition uses multiplication, so it does not depend on a convention for division by zero.
These definitions extend the published finite model and supply the common language of the two lower bounds; they impose no new restriction on a policy or profile.
import Mathlib
import Definitions.Def_ChangingCache_UpperBound_NormalForm
namespace ChangingCache.UpperBound.Supplement
/-- The first `r` requests of one infinite stream; includes the empty prefix. -/
def streamPrefix {α : Type*} (σ : ℕ → α) (r : ℕ) : List α :=
(List.range r).map σ
/-- One policy, with the same snapshots on every finite prefix. -/
def IsStreamLegal {α : Type*} [DecidableEq α] (m : ℕ → ℕ)
(σ : ℕ → α) (S : ℕ → Finset α) : Prop :=
∀ r, IsLegal m (streamPrefix σ r) S
/-- Definition 3.2 (= Definition 6.1), with real speed and signed real subtraction. -/
noncomputable def bank {α : Type*} [DecidableEq α] (s : ℝ) (m : ℕ → ℕ)
(σ : List α) (S : ℕ → Finset α) (r : ℕ) : ℝ :=
s * (policyMisses σ S r : ℝ) - (lruMissCount (augCap 2 s m) σ r : ℝ)
/-- Unbounded multiplicative makespan ratio, not an additive gap. Natural page names impose
no finite bound on the universe. OPT's denominator is strictly positive. -/
def UnboundedMakespanRatio (s : ℝ) : Prop :=
∀ R : ℝ, 0 < R → ∃ (m : ℕ → ℕ) (σ : List ℕ),
IsMemoryProfile m ∧ σ ≠ [] ∧ 0 < optMisses m σ ∧
R * s * (optMisses m σ : ℝ) < ((lruRun (augCap 2 s m) σ).misses : ℝ)
end ChangingCache.UpperBound.Supplement