Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Deterministic Causal Online Processes

Definition
pd_online_trace

by wenxinzhang · Aug 12, 2026 · Mathlib 0df444a (Lean v4.33.1)

competitive-analysisonline-algorithmsprimal-dualtransition-systems

This module provides a minimal interface for deterministic online algorithms.

An online process consists of request, state, and decision types, an initial state s0s_0s0​, and a transition map step ⁣:S×R→S×D\mathrm{step}\colon S\times R\to S\times Dstep:S×R→S×D that sees only the current state and the newly arriving request. For a finite request list r1,…,rnr_1,\dots,r_nr1​,…,rn​ the module defines the state reached after processing the list, the complete trace of post-transition states and decisions, and the list of decisions alone; each is available both from the designated initial state and from an arbitrary starting state.

The module proves two append laws: for all request lists HHH and TTT,

stateAfter(s, H+ ⁣ ⁣+T)  =  stateAfter(stateAfter(s,H), T),\mathrm{stateAfter}(s,\,H \mathbin{+\!\!+} T) \;=\; \mathrm{stateAfter}\bigl(\mathrm{stateAfter}(s,H),\,T\bigr),stateAfter(s,H++T)=stateAfter(stateAfter(s,H),T),

and the corresponding decomposition of traces. These laws express causality — an algorithm cannot inspect the future of the request stream — and they are the induction interface used by the load-balancing analysis to reason about prefixes of the arrival sequence.

Formalization Note Failure, rejection, and certificates are not built into the interface; they are represented in the user-chosen state and decision types. The two append laws are proved inside this definition module, so importing it makes them available without a separate theorem node.

Definition code
import Mathlib.Data.List.Basic

/-!
A deliberately small deterministic interface for online algorithms.

The transition sees only the current state and the newly arrived request.  Consequently every
value produced by `traceFrom` is causal by construction; an algorithm cannot inspect the suffix
of the request list.
-/

namespace PrimalDual.Online

/-- A deterministic online process.  Failure, rejection, and certificates can be represented in
the user-chosen `State` and `Decision` types rather than being built into the common interface. -/
structure Process (Request State Decision : Type*) where
  initial : State
  step : State → Request → State × Decision

namespace Process

variable {Request State Decision : Type*}

/-- The state reached after processing a finite request sequence, starting from `state`. -/
def stateAfterFrom (process : Process Request State Decision) : State → List Request → State
  | state, [] => state
  | state, request :: requests =>
      stateAfterFrom process (process.step state request).1 requests

/-- The state reached from the process's designated initial state. -/
def stateAfter (process : Process Request State Decision) (requests : List Request) : State :=
  process.stateAfterFrom process.initial requests

/-- The post-transition state and decision produced at every arrival. -/
def traceFrom (process : Process Request State Decision) :
    State → List Request → List (State × Decision)
  | _, [] => []
  | state, request :: requests =>
      let next := process.step state request
      next :: traceFrom process next.1 requests

/-- The complete post-transition trace from the designated initial state. -/
def trace (process : Process Request State Decision) (requests : List Request) :
    List (State × Decision) :=
  process.traceFrom process.initial requests

/-- Decisions produced from an arbitrary starting state. -/
def decisionsFrom (process : Process Request State Decision) (state : State)
    (requests : List Request) : List Decision :=
  (process.traceFrom state requests).map Prod.snd

/-- Decisions produced from the designated initial state. -/
def decisions (process : Process Request State Decision) (requests : List Request) :
    List Decision :=
  process.decisionsFrom process.initial requests

/-- Processing a prefix and then a suffix is the same as processing their concatenation. -/
theorem stateAfterFrom_append (process : Process Request State Decision) (state : State)
    (headRequests tailRequests : List Request) :
    process.stateAfterFrom state (headRequests ++ tailRequests) =
      process.stateAfterFrom (process.stateAfterFrom state headRequests) tailRequests := by
  induction headRequests generalizing state with
  | nil => rfl
  | cons request rest ih =>
      simp only [List.cons_append, stateAfterFrom]
      exact ih (process.step state request).1

/-- A trace over a concatenation is the prefix trace followed by the suffix trace started from
the prefix's final state.  This is the reusable causal-prefix law for later online proofs. -/
theorem traceFrom_append (process : Process Request State Decision) (state : State)
    (headRequests tailRequests : List Request) :
    process.traceFrom state (headRequests ++ tailRequests) =
      process.traceFrom state headRequests ++
        process.traceFrom (process.stateAfterFrom state headRequests) tailRequests := by
  induction headRequests generalizing state with
  | nil => rfl
  | cons request rest ih =>
      simp only [List.cons_append, traceFrom, stateAfterFrom, List.cons_append]
      exact congrArg (process.step state request :: ·) (ih (process.step state request).1)

end Process

end PrimalDual.Online
Source
Niv Buchbinder and Joseph (Seffi) Naor, The Design of Competitive Online Algorithms via a Primal--Dual Approach, https://www.tau.ac.il/~nivb/download/pd-survey.pdf, Section 2.3 (Online Computation), pp. 107--109; applied to irrevocable job assignments in the unrelated-machines problem discussed in Chapter 8.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me