Formal Reasoning about Performance Models
Moussa Labbadi, Rupak Majumdar, V. R. Sathiyanarayana, Sadegh Soudjani
cs.LO
Sep 29, 2026 · v1
cs.PF cs.PL
TL;DR
Implements the DES calculus and its proof rules as a shallow embedding in Lean 4 on Mathlib measure theory, with a custom tactic flauto.
Abstract
Discrete-event simulation is a standard technique for modelling and analysing the performance of computer systems, networks, and services. Although simulation tools are widely used, reasoning about the correctness and performance guarantees of the models they implement remains largely ad hoc: simulation outputs are interpreted statistically, but there is no logical foundation for deductive reasoning about their behaviour. We present a core imperative calculus that captures the essential constructs common to discrete-event simulators: asynchronous execution, continuous and discrete sampling from distributions, and time-based event scheduling through a global event queue. On top of this calculus, we develop a proof system for reasoning about almost-sure reachability and expected reaching time properties. Our main result is a sound and complete proof rule for these properties. Our framework generalizes deductive reasoning for discrete-time probabilistic programs to the setting of performance models, in which continuous time and continuous probability distributions are central. We have implemented the proof rules in a tool embedded in Lean. We demonstrate the applicability of our proof rule by deriving proofs of almost-sure reachability and expected reaching time for a number of case studies, including client-server examples that go beyond analytic solutions from queueing theory as well as convergence behaviours in network routing protocols. Establishing the soundness and completeness of our proof rules requires significantly more complex arguments than in the discrete-time setting. This is due to the fundamentally discontinuous nature of the operational semantics and the measure-theoretic challenges of continuous time and probability distributions.
Problem
Discrete-event simulation models of computer systems and networks are analysed empirically, with no deductive foundation for proving almost-sure reachability or expected reaching time under continuous time and continuous distributions.
Approach
The authors define DES, a core imperative calculus with asynchronous procedures, discrete and continuous sampling, and a global time-ordered event queue, with semantics given as a Markov process. They develop proof rules for almost-sure reachability and expected reaching time. They implement the rules in the tool Leonides as a shallow embedding in Lean 4 on Mathlib's measure theory. Proof obligations are emitted as goals and closed by a tactic, flauto, which uses search heuristics and SMT calls and is supplemented by user lemmas when needed.
Results
The proof rule is shown sound and complete. Case studies are fully formalized in Lean with no remaining sorry, using only the standard classical axioms. They include client-server systems beyond analytic queueing-theory results and the convergence of a stochastic network routing protocol.