Deterministic Causal Online Processes
Definitionpd_online_traceThis module provides a minimal interface for deterministic online algorithms.
An online process consists of request, state, and decision types, an initial state , and a transition map that sees only the current state and the newly arriving request. For a finite request list 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 and ,
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.
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