💻 computer science

Formally Verified Liveness with Multiparty Session Types in Rocq

This paper presents the first mechanized proof of liveness for synchronous multiparty session types in the Rocq Proof Assistant, utilizing coinductive trees and relations to formally verify the safety and liveness of communication protocols through approximately 14,000 lines of code.

Original authors: Omer Keskin, Nobuko Yoshida, Rob van Glabbeek

Published 2026-05-25

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Omer Keskin, Nobuko Yoshida, Rob van Glabbeek

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a group of friends trying to organize a complex dinner party where everyone needs to coordinate perfectly: who brings the wine, who cooks the main course, and who sets the table. If one person gets stuck waiting for a signal that never comes, the whole party grinds to a halt. In the world of computer science, this is called a "deadlock" or a "liveness" problem.

This paper is about building a mathematical guarantee that such coordination protocols will never get stuck. The authors have used a powerful tool called Rocq (a "proof assistant," which is like a super-strict robot mathematician) to prove that a specific method for designing these communication protocols works perfectly.

Here is the breakdown of their work using everyday analogies:

1. The Two Ways to Plan the Party

The paper discusses two ways to design these communication rules (called "Multiparty Session Types"):

The Bottom-Up Approach: You write down the rules for each individual person first, then try to check if they fit together. It's like asking everyone to write their own to-do list and then hoping they don't contradict each other.
The Top-Down Approach (The one this paper uses): You write one "Master Plan" (called a Global Type) that describes the entire party from a bird's-eye view. Then, you automatically generate a specific "Local Plan" for each person based on that Master Plan.

The authors chose the Top-Down approach because it's usually more efficient and ensures the rules are consistent from the start.

2. The "Translation" Problem

The tricky part is ensuring that the "Local Plans" generated for each person actually match the "Master Plan."

Imagine the Master Plan says: "Alice will send a message to Bob."
The Local Plan for Alice must say: "I will send a message to Bob."
The Local Plan for Bob must say: "I will wait for a message from Alice."

The paper introduces a special relationship called Association. Think of this as a translator that checks if the individual Local Plans are faithful copies of the Master Plan. If they are "associated," the robot mathematician (Rocq) knows they are safe to use.

3. The Three Big Guarantees

The authors proved that if you follow this Top-Down method and your plans are "associated," three magical things happen:

Safety (No Misunderstandings): If Alice tries to send a message, Bob is guaranteed to be listening for that specific type of message. They will never talk past each other.
Deadlock-Freedom (No Stuckness): The party will never reach a point where everyone is waiting for someone else to move first. If there is work to be done, someone will always be able to do it.
Liveness (No Starvation): This is the paper's main breakthrough. It guarantees that if a person is waiting to send or receive a message, that message will eventually happen. No one gets stuck waiting forever while the party continues without them.

4. How They Proved It (The "Robot" Work)

Proving "Liveness" is notoriously difficult because it involves infinite time (what happens if the party goes on forever?).

The Tree Metaphor: The authors represent the communication plans as infinite trees. A "Global Type" is a giant tree showing all possible future conversations.
The Grafting Trick: To prove the tree never gets stuck, they use a technique called "grafting." Imagine cutting a finite piece of the infinite tree (a "context") and proving that no matter how you fill in the missing holes, the logic holds up. It's like proving a bridge is safe by testing a small, removable section rather than the whole bridge at once.
The Fairness Assumption: They assume a "fair" world. In a fair world, if two people are ready to talk, they eventually will. They don't assume the universe is malicious; they just assume that if a door is open, someone will eventually walk through it.

5. The Result

The authors wrote about 14,000 lines of code in Rocq. This isn't just a theory; it's a verified, machine-checked proof.

They didn't just say, "It looks like it works."
They made the robot mathematician check every single step of the logic to ensure there are no holes in the argument.

Summary

In simple terms, this paper says: "We have built a robot-proof system that guarantees if you design your multi-person communication rules from a single Master Plan, everyone will get their turn to speak, no one will get stuck waiting forever, and everyone will understand each other."

This is the first time this specific "Liveness" guarantee has been fully verified by a computer proof assistant for this type of system, turning a complex mathematical concept into a certified, reliable fact.

Technical Summary: Formally Verified Liveness with Multiparty Session Types in Rocq

Problem Statement
Multiparty Session Types (MPST) provide a type discipline for specifying message-passing protocols involving multiple participants. While MPSTs are known to guarantee properties such as communication safety and deadlock-freedom, ensuring liveness (also referred to as lock-freedom or starvation-freedom) remains a significant challenge. Liveness requires that if a process is waiting to send or receive, a communication involving it eventually occurs. Existing literature often relies on informal proofs for liveness, particularly in the top-down approach where a global type is projected onto local types. Furthermore, while previous mechanisations of MPST exist (e.g., in Rocq/Coq), they have not yet provided a formal proof of liveness for synchronous multiparty sessions, nor have they mechanised the specific "association" relation that links local type environments to global types to guarantee these properties.

Methodology
The authors present a formalisation of a synchronous MPST system within the Rocq Proof Assistant (formerly Coq). The methodology relies on the following core components:

Coinductive Representation: Building on recent work by Ekici et al., the system represents global and local types as coinductive trees. This equirecursive approach allows for the direct manipulation of infinite type trees obtained by unfolding guarded syntactic types.
The Association Relation ( $\sqsubseteq$ ): The authors define a relation between a local type environment (a mapping of participants to local types) and a global type. This relation is established via:
- Projection: A coinductive plain-merge projection relating global types to local types.
- Subtyping: A coinductive subtyping relation on local types.
- Balancedness: A regularity condition on global types ensuring that every participant appears frequently enough on paths to prevent infinite starvation.
Operational Correspondence: The authors define Labelled Transition System (LTS) semantics for both local type environments and global types. They prove that if a local environment is associated with a global type, their reduction sequences correspond (soundness and completeness of association).
Liveness via Linear Temporal Logic (LTL) and Paco:
- Liveness and fairness are defined over execution traces (coinductive streams).
- The authors utilize the Paco library for parameterised coinduction. This allows them to define fairness and liveness predicates as mixed inductive-coinductive relations, avoiding the non-compositional syntactic guardedness checks of native cofix tactics.
- Fairness is formalised using LTL operators (specifically eventually and always), ensuring that enabled communications are eventually executed.
Grafting Technique: To handle proofs on infinite trees, the authors employ a "grafting" technique. They decompose balanced global types into finite "g-contexts" (prefixes with holes) and infinite subtrees. This allows proofs by coinduction on infinite trees to be transformed into proofs by induction on the height of finite g-contexts.

Key Contributions

First Mechanised Proof of Liveness: This work presents the first mechanised proof of liveness for synchronous multiparty session types in a proof assistant.
Mechanisation of the Association Relation: It is the first work to mechanise an MPST system based on the association relation between local type environments and global types, proving the correctness of the system by formalising properties of the local environments.
Formal Verification of Safety and Deadlock-Freedom: The authors prove that sessions typed by an associated local type environment are communication-safe and deadlock-free.
Operational Correspondence: The paper establishes a rigorous operational correspondence between the LTS of local type environments and global types, showing that reductions in one can be matched by reductions in the other.
Implementation: The formalisation consists of approximately 14,000 lines of Rocq code, available as open-source software.

Results
The authors prove three main theorems regarding sessions typed by local type environments associated with a balanced global type:

Communication Safety (Theorem 6.5): Typed sessions evolve such that if a participant attempts to send a message with a specific label, the receiving participant is capable of receiving that label.
Deadlock-Freedom (Theorem 6.6): A typed session either terminates or can always perform a reduction step; it never reaches a stuck state where no progress is possible.
Liveness (Theorem 6.9): If a session is typable by an associated environment, it is live. Specifically, if a participant is waiting to send or receive, a communication involving that participant eventually occurs, provided the execution path is fair.

The proof of liveness (Theorem 5.8 for environments and Theorem 6.9 for sessions) is identified as the most intricate result. It proceeds by first proving liveness for the "direct projection" of the global type, and then using the association relation to lift this property to any associated local environment. The proof relies on an induction invariant based on the height of the "grafting" of the global type.

Significance and Claims
The paper claims that its primary significance lies in clarifying often informal proofs found in MPST literature and providing a certified foundation for liveness properties in communication protocols. By moving from pencil-and-paper proofs to a machine-checked formalisation, the work eliminates potential gaps in reasoning regarding infinite behaviors and fairness assumptions.

The authors note that their approach using parameterised coinduction and LTL results in compositional and clear proofs, which are difficult to achieve with standard syntactic guardedness checks. They position this work as a framework that can potentially be extended to other process calculi (like the $\pi$ -calculus) or different fairness assumptions, provided the core operational correspondence properties hold. The work does not claim to solve liveness for all process calculi or to provide a general algorithm for liveness checking, but rather establishes a verified type system for a specific synchronous MPST calculus.