rank_potential
def
The rank potential function Φ for FIFO paging, defined as the sum of ranks of all pages currently in the online FIFO cache but absent from the offline cache.
Statement
def rank_potential {α : Type*} [DecidableEq α] {k : ℕ} (q : FifoQueue α k) (cOpt : Finset α) : ℕ
- Defined in
- arXiv:2610.18767 Section 3.2, Eq. (1)
- Verified
- 20 Oct 2026
- Axioms
- none listed
- Built on 2
- Used by 4
- rank_potential_offline_fetch_boundAt an offline fetch, the increase in rank potential is at most k (Lemma 3.3(i)).
- rank_potential_zero_of_subsetIf all pages in the online FIFO cache are present in the offline cache, the rank potential Φ is zero; in particular, the initial potential…
- rank_potential_online_payment_boundFor any type α with decidable equality, any k ≥ 1, any FIFO queue q of capacity k, any offline cache cOpt of cardinality k, and any page v…
- rank_potential_offline_evict_hole_boundAt an offline fetch, if the evicted page is outside the online cache, the change in rank potential is at most 0 (Lemma 3.3(ii)).
Read back from the Lean
For a type α with decidable equality, an implicit natural number k, a FIFO queue q : FifoQueue α k (a structure containing a list q.pages of length k with pairwise distinct elements), and a finite set cOpt : Finset α, rank_potential q cOpt is defined as the natural number obtained by summing fifo_rank q x over all elements x in the set difference q.pages.toFinset \ cOpt.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Rank potential Φ summing ranks of online cached pages outside offline cache. -/ def rank_potential {α : Type*} [DecidableEq α] {k : ℕ} (q : FifoQueue α k) (cOpt : Finset α) : ℕ := ∑ x ∈ q.pages.toFinset \ cOpt, fifo_rank q x