TL;DR
The TLA+ Toolbox has gained the ability to support liveness proofs, prompting a re-evaluation of the Xen vchan protocol specification. The author walks through a simple channel model and the practical challenges of encoding and discharging temporal claims with TLAPS, noting solver limitations and proof patterns that make progress possible but sometimes awkward.
What happened
The author revisited an earlier TLA+ specification for the Xen vchan communication protocol after TLAPS added more complete temporal-logic support. They started by modeling a one-way channel with variables tracking bytes sent and received and a bounded buffer, then expressed the target liveness property: any amount sent should eventually be received. The post outlines how to write Init, Send and Recv actions and compose them into Spec with weak fairness for Recv. The author used the model checker (TLC) to validate small instances before attempting machine-checked proofs. Invariant proofs were handled with standard action-based reasoning, while liveness required more careful use of temporal logic and TLAPS’ PTL procedure. The write-up explains coalescing behavior (TLAPS replacing modal parts for backends), generalisation issues when assumptions are introduced, and several proof workarounds and gotchas encountered while scaling from the toy model toward the real protocol.
Why it matters
- Tool support for temporal logic widens the class of properties (like liveness/availability) that can be machine-verified in TLA+.
- Proving liveness complements model checking: TLC tests behaviours on bounded models, while TLAPS can produce machine-checked proofs for full specifications.
- Understanding TLAPS’ handling of modal formulas and its backend limitations is essential for structuring proofs that actually verify progress properties.
- Practical quirks and bugs mean engineers must adapt proof structure (lemmas, SUFFICES, non-modal steps) rather than rely on a single automatic step.
Key facts
- The TLA+ Toolbox now supports proving liveness properties using TLAPS’ enhanced temporal-logic capabilities.
- The author applied the feature to a simple one-way channel model and to the Xen vchan protocol specification previously developed in 2018.
- Channel state is represented by Sent and Got counters, with BufferUsed = Sent – Got and BufferFree = BufferSize – BufferUsed.
- Liveness is formalised as: for every natural number n, if Sent = n then eventually Got >= n.
- System dynamics are given by Send and Recv actions; Spec combines Init, the step relation, and WF_vars(Recv) to enforce receiver progress.
- Basic invariants (variable domains, Sent >= Got, buffer bounds) are proved with ordinary action reasoning and require only one temporal step in the proof.
- TLAPS uses a PTL module for propositional temporal logic but its other backends do not understand modal operators or certain arithmetic, leading to a coalescing strategy that replaces complex subformulas with fresh blobs.
- Proofs often must be reorganised into non-modal lemmas or use SUFFICES to allow PTL to generalise obligations; several practical bugs and syntax sensitivities were encountered.
What to watch next
- Whether remaining TLAPS solver limitations and the specific bugs noted get fixed in future releases — not confirmed in the source.
- Progress on a complete, machine-checked Availability proof for the full Xen vchan protocol using the new temporal capabilities — not confirmed in the source.
- Adoption of the Toolbox temporal features by other protocol verifiers and any published patterns or libraries to ease temporal proofs — not confirmed in the source.
Quick glossary
- TLA+: A specification language for describing concurrent and distributed systems using mathematical sets and temporal logic.
- TLAPS: The TLA+ Proof System, a toolchain for producing machine-checked proofs of properties of TLA+ specifications.
- TLC: The TLA+ Model Checker, which explores finite instances of a specification to find counterexamples and validate behaviours.
- Liveness: A class of temporal properties that assert something good eventually happens (e.g., messages sent are eventually received).
- Weak fairness (WF): A fairness condition that requires an action to occur eventually if it remains continuously enabled.
Reader FAQ
What changed in the Toolbox?
The Toolbox now supports proving liveness properties by leveraging TLAPS’ improved temporal-logic handling.
Can TLAPS now prove Availability for the Xen vchan protocol?
not confirmed in the source
How should I structure temporal proofs in TLAPS?
Break proofs into non-modal lemmas where possible, use PTL for the final temporal reasoning step, and introduce assumptions (e.g., SUFFICES) carefully so obligations can be generalised.
Is model checking enough to guarantee correctness?
Model checking (TLC) is useful for testing bounded instances, but it does not replace full machine-checked proofs for unbounded liveness or invariants.
Proving liveness with TLA 2026-01-01 The TLA Toolbox now has support for proving liveness properties (i.e. that something will eventually happen). I try it out on the Xen vchan protocol….
Sources
- Proving Liveness with TLA
- TLA+ Proofs?
- TLAPS supports temporal reasoning. I've personally used it …
- TLA+ Proofs – Leslie Lamport
Related posts
- Blaze: Rust-based emulator revives DEC VT420 terminal hardware and more
- A Basic Just-In-Time Compiler: building x86-64 JIT for recurrence relations
- Southern Madagascar’s parched communities face isolation, hunger and drought