Call-record invariants of recursive PageRank executions
ProvedNearlyOptimalPPR.Computation.recursive_call_metadataAt every finite prefix of the operational recursive computation, the call records satisfy the following invariant:
Its scale and block size agree with the frame at that level. Recorded, open and closed call identifiers are below the next fresh identifier; every open frame has the corresponding information record. While the computation is running, open frames are not recorded as closed.
These properties permit tracking a single call through interruptions, child returns, and finite-prefix accounting, without assuming that it eventually closes.
Formalization Note Call identifiers and information records are bookkeeping in the operational translation of Algorithms 6–9. The theorem proves their preservation; no correctness or running-time guarantee is built into the record assumptions.
import Definitions.Def_NearlyOptimalPPR_Computation_work_analysis set_option autoImplicit false open Finset Matrix NearlyOptimalPPR.Computation
theorem NearlyOptimalPPR.Computation.recursive_call_metadata (m : SolveModel) (n : ℕ) (g : InputGraph n) (s : Fin n) (α q : ℝ)
(ℓ : ℕ) (schedule : BlockSchedule) (t : ℕ) :
let st := recursiveRun m g s α q ℓ schedule t
CallLocations st ∧ InformationIDBound st ∧ OpenIDBound st ∧ ClosedIDBound st ∧
OpenFrameInformation st ∧ RunningOpenNotClosed st := by sorry