Proving liveness with TLA

Summary

The article discusses using TLA+ to prove liveness properties, focusing on a simple channel specification and the Xen vchan protocol. It covers temporal logic, proving temporal claims with TLAPS, and workarounds for bugs in TLAPS. The author provides examples and explanations to illustrate the concepts.

Key Takeaways

1. The TLA Toolbox now has support for proving liveness properties (i.e. that something will eventually happen).
2. Newer versions of TLAPS (the TLA Proof System) have added proper support for temporal logic, so I decided to take another look.
3. The main problem is that TLA propositions are written in First Order Modal Logic, but TLAPS doesn't have any solvers that understand this!

Statement Breakdown

• Claimed Facts: 60% of statements the article presents as facts
• Opinions: 25% of statements classified as editorial or subjective
• Claims: 15% of statements surfaced for additional reader evaluation

Credibility & Bias Reasoning

Credibility assessment: The article is a technical blog post by an author with apparent expertise in the subject matter (TLA+). The author references their previous work and provides specific examples and code snippets. The article also acknowledges bugs and limitations in the tools being discussed, enhancing credibility.

Bias assessment: Technical Explanation. The article focuses on explaining a specific technology (TLA+) and its application to proving liveness properties. The author's primary goal is to educate the reader on the technical aspects of the subject, rather than promoting a particular viewpoint or agenda. The tone is informative and objective.

Note: This article presents technical information and personal experiences. Verify claims and consider the author's expertise when evaluating the content.

Credibility flag: Technical, Informative

Claimed Facts (7)

• This is a statement of fact about the vchan protocol.
• This is a factual account of the author's previous work.
• This describes a specific aspect of the model.
• This describes the initial state of the system.
• This defines the condition for the Send action.
• This defines the condition for the Recv action.
• This explains the concept of worlds in TLA.

Opinions (6)

• This is a subjective assessment of what is useful.
• This is a subjective assessment of what is good practice.
• This is a subjective assessment of the best approach.
• This is a subjective assessment of the difficulty of certain steps.
• This is a subjective assessment of TLAPS's usability.
• This is a subjective assessment of what would be a desirable feature.

Claims (6)

• This statement is vague and lacks specific evidence or quantification of "very little temporal logic".
• The claim that it's "likely to spot most problems" is not substantiated.
• The author admits to only having a "rough understanding", making this a potentially unreliable claim.
• The claim of unreliability is based on a specific bug, but the extent of the unreliability is not quantified.
• This anecdotal evidence is not a rigorous proof of a bug.
• While a screenshot is provided, the context and implications of this specific case may not be generalizable.

Key Sources

• Thomas Leonard — Author