Reasoning about concurrent loops and recursion with rely-guarantee rules

2026-06-12 · Source: cs.SE updates on arXiv.org · Field: Technology & Digital — Software Development & Engineering, Formal Methods, Concurrency Theory · Depth: Expert, extended

Summary

This paper from The University of Queensland presents mechanically verified refinement rules for reasoning about recursive programs and while loops in concurrent contexts. Unlike many existing approaches, this work does not assume atomic expression evaluation, instead employing a fine-grained definition of expressions and compositional inference rules. It utilizes the rely-guarantee approach to manage interference from concurrent threads. The authors define recursive programs and loops as greatest fixed points over a command lattice, developing laws for reasoning about these fixed points. A key contribution is an "early termination" version of the loop inference rule, which accounts for scenarios where interference, rather than the loop body, causes termination. The framework, including its lemmas and theorems, has been formally proven within the Isabelle/HOL theorem prover.

Key takeaway

For software engineers developing or verifying concurrent systems, this work provides a robust formal framework to reason about loops and recursion without relying on unrealistic atomic operation assumptions. You should consider adopting rely-guarantee conditions and the "early termination" loop rule to accurately model and prove termination for complex concurrent algorithms, especially those involving fine-grained shared memory access or compare-and-swap operations. This approach, verified in Isabelle/HOL, offers a higher assurance level for critical concurrent code.

Key insights

Mechanically verified rely-guarantee rules enable compositional reasoning for concurrent loops and recursion without assuming atomic expression evaluation.

Principles

• Concurrency verification requires non-atomic expression evaluation.
• Rely-guarantee conditions facilitate compositional interference reasoning.
• Loops and recursion can be modeled as greatest fixed points.

Method

The approach extends sequential refinement calculus with Aczel trace semantics, defining commands as a complete lattice. It uses Hoare triples and stability properties for preconditions, applying well-founded induction with variant expressions for termination.

In practice

• Verify concurrent while loops using the "early termination" rule.
• Apply compositional rules for expressions with multiple shared variable references.
• Model concurrent set operations like remove with CAS.

Topics

• Concurrent Programming
• Formal Verification
• Rely-Guarantee Reasoning
• Program Refinement
• Isabelle/HOL
• Loop Termination
• Recursion Theory

Best for: Research Scientist, AI Scientist, Software Engineer

Related on AIssential

• Protecting Language Models Against Unauthorized Distillation through Trace Rewriting — Reasoning trace rewriting can effectively deter unauthorized LLM distillation and embed verifiable watermarks without degrading teacher performance.
• Isabelle/HOL: The proof assistant behind the Nitro Isolation Engine — Isabelle/HOL's balance of expressiveness and automation enabled the formal verification of AWS's Nitro Isolation Engine.
• State Representation and Termination for Recursive Reasoning Systems — Explicit state representation and an order-gap termination criterion enhance recursive reasoning systems' efficiency and reliability.
• C++26: Reflection, Memory Safety, Contracts, and a New Async Model — C++26 standardizes reflection, enhances memory safety, adds contracts, and unifies asynchronous programming for robust, performant code.
• How Tool Chaining Fails in Production LLM Agents and How to Fix It — Tool chaining in LLM agents often fails silently in production due to cascading errors and context loss.
• Your AI Just Wrote 500 Lines of Code. Can You Prove Any of It Works? — A framework classifies AI-generated code by its formal verifiability based on five structural properties.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by cs.SE updates on arXiv.org.