Model Checking Probabilistic Multiparty Session Types

arXiv:2611.14795 · cs.PL · Submitted 2026-11-10 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "Model Checking Probabilistic Multiparty Session Types".

Jane: Here's the gist of the paper. This paper introduces a novel probabilistic extension of general multiparty session types, developed bottom-up without requiring a global specification, enabling quantitative derivation of session properties solely from their types.

Tom: These types integrate probabilistic choice with nondeterministic choice to abstract data-dependent control and permit separated choices involving different participants.

Jane: The work establishes a new probabilistic subtyping relation and merge operator to rigorously prove type soundness and session fidelity.

Tom: The semantics of typing contexts are formally defined as a finite Markov Decision Process (MDP).

Title and authors: Tom: Moving into the summary of Model Checking Probabilistic Multiparty Session Types, this paper basically sets up this new framework to derive quantitative properties of session processes directly from their types.

Jane: It says they define the semantics of typing contexts as a finite Markov Decision Process or MDP, and then from that MDP, they can derive sound lower bounds on the probability that a session is deadlock-free and live under any fair adversarial scheduler.

Lu: The core idea here is taking these typing contexts, which are essentially these MDPs, and using them to get sound lower bounds on properties like deadlock-freedom and liveness across all possible fair schedulers.

Meng: But the paper also introduces a translation from these session types into the PRISM modeling language, which has been proven sound and complete with respect to operational semantics, giving us a practical way to check things in practice.

Lalam: So it’s not just theory; they are providing a concrete translation tool that lets you translate those abstract session types into something you can actually model and verify using PRISM for safety and liveness checks.

Tom: It seems like the main takeaway here is that we can use these types to get reliable numbers on how likely a session is to fail or succeed under different timing scenarios, which is much more useful than just saying it's *probably* safe.

Jane: So, instead of just hoping the system works okay in practice, we get mathematical guarantees about the probability of it being deadlock-free or live based on these types.

Lu: The paper’s focus is on establishing this new probabilistic extension of general multiparty session types bottom-up, without needing a global specification upfront.

Meng: That bottom-up approach is appealing because it means we can analyze the system piece by piece, and the type system does all the heavy lifting for us regarding the properties.

Lalam: The authors are proposing a new probabilistic subtyping relation and merge operator that rigorously proves type soundness and session fidelity, which is crucial for ensuring these derived properties hold up when you combine different session components.

The paper's summary: Tom: So what the paper actually proposes as improvements to existing work is really this novel probabilistic extension of generalized multiparty session types that allows them to derive quantitative properties solely from the types.

Jane: They’ve integrated probabilistic choice with nondeterministic choice into these types, which serves to abstract away data-dependent control and also lets you have separated choices involving different participants.

Lu: This is a step up because it moves beyond previous systems by allowing this kind of combination, which was previously hard to capture probabilistically in a multiparty setting.

Meng: From my perspective on deployment, the paper handles data-dependent control flow by replacing it with nondeterministic choices in types, which accounts for different outcomes from tests while still keeping the probability information from flips.

Lalam: They are showing that a typing context yields sound lower bounds on the probabilistic properties of typed session processes, specifically proving that if you have a typing context delta and a process M, then if delta implies M, the deadlock-freedom of delta implies the deadlock-freedom of M.

Tom: That's really strong because it means properties like deadlock-freedom and liveness transfer from the typing context to the session under subtyping, which is a massive step in verification.

Jane: They also introduced this quantification method where you interpret the typing context as an MDP and use cylinder sets to define path probabilities under a scheduler, taking the minimum over all fair schedulers to get lower bounds.

Lu: The complexity analysis is interesting because they confirm that safety, deadlock-freedom, and liveness can be computed in time polynomial in the number of reachable states and transitions.

Meng: But we have to keep an eye on those complexity results; polynomial time is good for theory, but if the number of reachable states gets huge in a real system, we need to know how that scales practically.

The paper's improvements: Tom: So wrapping up this talk on Model Checking Probabilistic Multiparty Session Types, the main implication is that we can now use session types to get quantitative bounds on deadlock-freedom and liveness under every fair adversarial scheduler.

Jane: Essentially, if you have these session types, you don't just get a yes or no answer about safety; you get a number telling you the probability of it being safe or live.

Lu: The paper provides tools to analyze data-dependent control flow by abstracting it into nondeterministic choices in the types while preserving the probability information from those flips, which helps us model uncertainty more accurately.

Meng: For deployment, this means we can use tools like Prose to translate these session types into PRISM and check these probabilistic properties for safety and liveness before we even write a single line of production code.

Lalam: The paper establishes that the quantification of these properties is achieved by interpreting the typing context as an MDP, using cylinder sets to define path probabilities under a scheduler, and taking the minimum over all fair schedulers to obtain lower bounds for things like Pmin df delta equal one minus max phi in Phi delta p phi delta deadlock.

Tom: It’s about getting that bound, not necessarily the exact probability of failure, which is a practical trade-off explained by how conditional choices are abstracted into non-deterministic choices under the worst-case scheduler.

Jane: So it gives us a way to verify if a typed multiparty session is almost surely deadlock-free or almost surely live by computing that Pmin df delta value.

Lu: And while the paper states that type checking is decidable, we should remember that this method yields lower bounds rather than exact probabilities, which is important context for how we apply it in real-world scenarios.

Meng: I’m just thinking about what this means for the actual cost of running these checks; if those polynomial complexity results hold up on large systems, it could be very useful for scaling verification processes.

Lalam: The paper itself notes that they are laying the first groundwork for this type of quantitative verification, which is a big deal in making distributed systems more reliable.

Conclusion: Tom: So we talked about how session types can now give us actual numbers on how likely a session is to be deadlock-free or live, and this paper, "Model Checking Probabilistic Multiparty Session Types," shows that this framework works by using a finite Markov Decision Process for the typing context.

Jane: It’s really about taking these abstract session types and turning them into something you can model in a tool like PRISM to check safety and liveness with actual calculated bounds, not just guesses.

Lu: I think the most interesting part is that they introduce a new probabilistic subtyping relation, which lets you rigorously prove that if one type implies another, then the properties of the first type are inherited by the second.

Meng: From a deployment angle, it means we can get these quantitative guarantees for concurrent systems without having to run an impossibly long exact simulation; you get a bound in polynomial time related to your states and transitions.

Lalam: I’m pretty sure this is solid because they proved that if you have a typing context delta and a process M, and delta implies M, then the minimum probability of deadlock for delta is less than or equal to the minimum probability of deadlock for M.

Tom: That transfer under subtyping is key; it means if your overall system structure has a certain level of safety in its types, any smaller part you add stays safe too.

Jane: And they show you how to get that bound by treating the typing context like an MDP and looking at the minimum probability over all fair schedulers.

Lu: They also connect this to AI systems by showing that analyzing these typing contexts as MDPs lets us derive sound lower bounds on deadlock-freedom and liveness under any fair adversarial scheduler.

Meng: It’s good to see how AI is being used here, not just for generating the types, but for doing the deep analysis of what those types actually mean in terms of system behavior.

Tom: So this paper gives us a way to move from just saying a system is "probably safe" to knowing exactly what the probability of failure is under any timing scenario.

Jane: It’s a big step toward making probabilistic verification practical for complex, concurrent systems that we see everywhere in modern software.

Lu: This work sets up the foundation for how we can quantify control flow based on data-dependent choices by replacing them with nondeterministic choices in the types, which keeps the probability information alive through those flips.

Meng: The complexity analysis confirms that you can compute these bounds efficiently, and it scales reasonably well with more participants and states.

Lalam: Overall, "Model Checking Probabilistic Multiparty Session Types" provides a concrete mathematical foundation for deriving these probabilistic properties directly from the session types themselves.

University of Oxford

cs.PL

Submitted: 2026-11-10

Updated: 2026-11-10

Comments: 108 pages, full version of "Model Checking Probabilistic Multiparty Session Types" appearing at POPL 2027

Project page: https://www.stormchecker.org

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 98/100

The gist: This paper introduces a novel probabilistic extension of general multiparty session types, developed bottom-up without requiring a global specification…

Key concepts

Probabilistic Extension of Session Types
This is a novel type system that combines probabilistic choice with nondeterministic choice to handle complex session interactions. It allows session types to model data-dependent control by abstracting it into non-deterministic choices, while still retaining probability information from 'flip' constructs.
Typing Context as MDP
The semantics of typing contexts are formally defined as a finite Markov Decision Process (MDP). This mathematical structure is used to analyze session behavior. From this MDP, the authors can derive sound lower bounds on the probability that a session will be deadlock-free or live, even when facing an adversarial scheduler.
Lower Bounds on Properties
The system provides quantitative guarantees rather than exact probabilities. By interpreting the typing context as an MDP and taking the minimum over all fair schedulers, it yields lower bounds for properties like deadlock-freedom (e.g., Pmin df). This means the session is guaranteed to be deadlock-free with a certain probability threshold.
Translation to PRISM
A translation exists from these session types into the PRISM modeling language. This translation is proven sound and complete, meaning that checking safety, deadlock-freedom, and liveness in PRISM using these types will accurately reflect the properties of the actual session processes.

Terminology

Summary

This paper introduces a novel probabilistic extension of general multiparty session types, developed bottom-up without requiring a global specification, enabling quantitative derivation of session properties solely from their types. p. 0

Where the paper says it

Model Checking Probabilistic Multiparty Session Types ALEKSANDER JUNGE∗ and LEO SEOJUN LEE∗ , University of Oxford, UK JOSEPH PAULUS, NOBUKO YOSHIDA, and DAVID PARKER, University of Oxford, UK Distributed systems increasingly rely on randomisation; yet, verification techniques for such systems remain separate from the programming abstractions used to build them. This paper proposes the first probabilistic extension of general multiparty session types — typing sessions bottom-up, with no global specification — deriving quantitative properties of a multiparty session from its session types alone.

These types integrate probabilistic choice with nondeterministic choice to abstract data-dependent control and permit separated choices involving different participants. p. 0
Where the paper says it

This paper proposes the first probabilistic extension of general multiparty session types — typing sessions bottom-up, with no global specification — deriving quantitative properties of a multiparty session from its session types alone. Our types combine probabilistic choice with nondeterministic choice that abstracts data-dependent control, and allow separated choices, where each branch of a selection or branching may involve a different participant — a combination beyond previous probabilistic multiparty session type systems.

The work establishes a new probabilistic subtyping relation and merge operator to rigorously prove type soundness and session fidelity. p. 0
Where the paper says it

Our types combine probabilistic choice with nondeterministic choice that abstracts data-dependent control, and allow separated choices, where each branch of a selection or branching may involve a different participant — a combination beyond previous probabilistic multiparty session type systems. To achieve this, we develop a novel probabilistic subtyping relation and merge operator, using which we prove type soundness and session fidelity.

The semantics of typing contexts are formally defined as a finite Markov Decision Process (MDP). p. 0

Where the paper says it

To achieve this, we develop a novel probabilistic subtyping relation and merge operator, using which we prove type soundness and session fidelity. The semantics of typing contexts separates nondeterministic resolution, probabilistic choice, and synchronisation, so that every typing context induces a finite Markov decision process.

From this MDP, sound lower bounds on the probability that a session is deadlock-free and live are derived under every fair adversarial scheduler. p. 0
Where the paper says it

The semantics of typing contexts separates nondeterministic resolution, probabilistic choice, and synchronisation, so that every typing context induces a finite Markov decision process. On it, we derive sound lower bounds, holding under every fair adversarial scheduler, on the probability that a session is deadlock-free and live — the first behavioural property guarantees, partial or otherwise, for a probabilistic session calculus.

A translation from these session types into the PRISM modelling language is introduced, which has been proven sound and complete with respect to operational semantics and implemented in the Prose toolchain for practical verification of safety, deadlock-freedom, and liveness. p. 0
Where the paper says it

To connect session types with probabilistic model checking, we introduce the first translation from session types into the PRISM modelling language, and prove it sound and complete with respect to our operational semantics. We implement the framework in the toolchain Prose, which translates probabilistic multiparty session typing contexts into PRISM and checks safety, deadlock-freedom, and liveness.

The core contributions include:

  1. Proposing the first probabilistic extension of generalized (bottom-up) multiparty session types. p. 0

    Where the paper says it

    Model Checking Probabilistic Multiparty Session Types ALEKSANDER JUNGE∗ and LEO SEOJUN LEE∗ , University of Oxford, UK JOSEPH PAULUS, NOBUKO YOSHIDA, and DAVID PARKER, University of Oxford, UK Distributed systems increasingly rely on randomisation; yet, verification techniques for such systems remain separate from the programming abstractions used to build them. This paper proposes the first probabilistic extension of general multiparty session types — typing sessions bottom-up, with no global specification — deriving quantitative properties of a multiparty session from its session types alone.

  2. Proving that a typing context yields sound lower bounds on the probabilistic properties of typed session processes (deadlock-freedom and liveness). p. 3

    Where the paper says it

    Contributions and Outline. To the best of our knowledge, this work is the first to propose a probabilistic extension of generalised (bottom-up) multiparty session types, to prove that a typing context yields sound lower bounds of probabilistic properties of typed session processes, and to translate session types into a probabilistic modelling language with proofs of soundness and completeness with respect to operational semantics.

  3. Introducing the first translation from session types into a probabilistic modelling language with proofs of soundness and completeness relative to operational semantics. p. 3

    Where the paper says it

    Contributions and Outline. To the best of our knowledge, this work is the first to propose a probabilistic extension of generalised (bottom-up) multiparty session types, to prove that a typing context yields sound lower bounds of probabilistic properties of typed session processes, and to translate session types into a probabilistic modelling language with proofs of soundness and completeness with respect to operational semantics.

The analysis demonstrates that type checking is decidable (Theorem 3. p. 3

Where the paper says it

8), which reconciles the two outcomes of a flip. We further demonstrate that type checking is decidable (Theorem 3.

14). Crucially, the main theorems show that properties like deadlock-freedom and liveness transfer from the typing context to the session under subtyping (delta M: delta). p. 3
Where the paper says it

6), and proves the main results: a typing context induces lower bounds on the probabilities of deadlock-freedom (Theorem 4. 26) and liveness (Theorem 4.

Specifically, Theorem 4. p. 3
Where the paper says it

We therefore characterise probabilistic deadlock-freedom as a safety property over finite paths that PRISM checks without any fairness constraint. Characterising liveness in this manner is more challenging: to do this, we introduce the notion of a weak almost-sure livelocked region, and prove that the maximum probability of reaching this region corresponds exactly to the minimum probability that the typing context is live (Theorem 6.

26 proves that if M: delta, then df(delta) implies df(M), and P df(delta) at most P df(M). p. 9
Where the paper says it

ℓ⟨B⟩ −−−−−−→1 and Δ q:p? ℓ ′ (B ′ ) −−−−−−−→1 imply Δ (p,q)ℓ −−−−→1; (3) Δ −→ Δ ′ implies 𝜑(Δ ′ ) We write safe(Δ) if 𝜑(Δ) holds for some safety property 𝜑.

Similarly, Theorem 4. p. 3
Where the paper says it

We therefore characterise probabilistic deadlock-freedom as a safety property over finite paths that PRISM checks without any fairness constraint. Characterising liveness in this manner is more challenging: to do this, we introduce the notion of a weak almost-sure livelocked region, and prove that the maximum probability of reaching this region corresponds exactly to the minimum probability that the typing context is live (Theorem 6.

27 relates liveness properties. p. 7
Where the paper says it

5], we require the set of participants {pi}𝑖∈𝐼 be identical to {pi}𝑖∈𝐼∪𝐽 for downward-closure for typing context properties (Lemma C. [sub-⊕] relates two selection distributions only when targets, labels, sorts, and probabilities coincide (changing any would be observable and break substitutability).

The quantification of these properties is achieved by interpreting the typing context as an MDP, using cylinder sets to define path probabilities under a scheduler, and taking the minimum over all fair schedulers to obtain lower bounds. p. 3

Where the paper says it

We define the probability of a set of paths under a fixed scheduler by standard means, using cylinder sets (Def. 7), and obtain lower bounds by taking the minimum over all fair schedulers (Def.

The probabilistic multiparty session calculus (promtcalculus) is defined with a single probabilistic construct flip(p), where properties like deadlock-freedom and liveness are expressed in terms of the minimum probability over fair schedulers. p. 3
Where the paper says it

To the best of our knowledge, this work is the first to propose a probabilistic extension of generalised (bottom-up) multiparty session types, to prove that a typing context yields sound lower bounds of probabilistic properties of typed session processes, and to translate session types into a probabilistic modelling language with proofs of soundness and completeness with respect to operational semantics. § 2 proposes a probabilistic multiparty session calculus (promt) as a conservative extension of synchronous multiparty session processes in [22], with a single probabilistic construct flip(𝑝){h⇒𝑃 [] t⇒𝑄}, and proves that safety of sessions is undecidable (Proposition 2.

The complexity analysis confirms that safety, deadlock-freedom, and liveness can be computed in time polynomial in the number of reachable states and transitions. p. 0

Where the paper says it

To connect session types with probabilistic model checking, we introduce the first translation from session types into the PRISM modelling language, and prove it sound and complete with respect to our operational semantics. We implement the framework in the toolchain Prose, which translates probabilistic multiparty session typing contexts into PRISM and checks safety, deadlock-freedom, and liveness.

The verification approach yields lower bounds for these properties rather than exact probabilities, a trade-off explained by how conditional choices are abstracted into non-deterministic choices under the worst-case scheduler. p. 2
Where the paper says it

We analyse it under the least favourable (adversarial) resolutions of nondeterminism, subject to our fairness assumptions. This accounts for the information lost through abstraction and yields sound lower bounds on the probabilities of properties of the original session.

The toolchain Prose facilitates practical checking, with complexity results showing that properties can be computed in time polynomial in N, R, and delta, and Corollary 6. p. 0
Where the paper says it

To connect session types with probabilistic model checking, we introduce the first translation from session types into the PRISM modelling language, and prove it sound and complete with respect to our operational semantics. We implement the framework in the toolchain Prose, which translates probabilistic multiparty session typing contexts into PRISM and checks safety, deadlock-freedom, and liveness.

7 shows computation time polynomial in delta O(k), where k is the number of participants. p. 5
Where the paper says it

The server waits for one of two external choices: (1) incr from u, after which it sends incr⟨e⟩ to c and loops; or (2) an error(𝑥) from the calculator c on a previous computation upon which it retries the calculation by sending incr⟨𝑥⟩ to c again. The calculator is accurate up to a certain integer size — if the input from s is smaller than 2 8 , c successfully increments 𝑥 and forwards it to u, on the other hand if the number is greater than or equal, it has a 0.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Probabilistic verification of concurrent systems can be achieved by translating session types into a probabilistic modelling language like PRISM, which allows for checking safety, deadlock-freedom, and liveness based on derived lower bounds.

  2. AI systems can derive sound lower bounds on the probability that a session is deadlock-free and live under every fair adversarial scheduler by analyzing the finite Markov decision process induced by typing contexts.

  3. The system can verify if a typing context induces sound lower bounds of probabilistic properties of typed session processes, such as deadlock-freedom (Theorem 4.26) and liveness (Theorem 4.27).

  4. The framework supports the analysis of data-dependent control flow by replacing it with nondeterministic choices in types, which accounts for the possible outcomes of tests while retaining probability information from flips.

  5. The system can provide quantitative bounds on properties like deadlock-freedom and liveness over all fair schedulers, quantified by Pmin df (Delta) = 1 - max phi in Phi Delta P phi Delta (deadlock).

  6. The toolchain Prose can be used to translate typing contexts into PRISM and check safety, deadlock-freedom, and liveness for session types.

  7. The system can provide a means to verify if a typed multiparty session is almost-surely deadlock-free or almost-surely live by computing Pmin df (Delta) = 1 - Pmax (□“deadlock” ∧ ¬“end”).

Abstract

Distributed systems increasingly rely on randomisation; yet, verification techniques for such systems remain separate from the programming abstractions used to build them. This paper proposes the first probabilistic extension of general multiparty session types - typing sessions bottom-up, with no global specification - deriving quantitative properties of a multiparty session from its session types alone. Our types combine probabilistic choice with nondeterministic choice that abstracts data-dependent control, and allow separated choices, where each branch of a selection or branching may involve a different participant - a combination beyond previous probabilistic multiparty session type systems. To achieve this, we develop a novel probabilistic subtyping relation and merge operator, using which we prove type soundness and session fidelity. The semantics of typing contexts separates nondeterministic resolution, probabilistic choice, and synchronisation, so that every typing context induces a finite Markov decision process. On it, we derive sound lower bounds, holding under every fair adversarial scheduler, on the probability that a session is deadlock-free and live - the first behavioural property guarantees, partial or otherwise, for a probabilistic session calculus. To connect session types with probabilistic model checking, we introduce the first translation from session types into the PRISM modelling language, and prove it sound and complete with respect to our operational semantics. We implement the framework in the toolchain Prose, which translates probabilistic multiparty session typing contexts into PRISM and checks safety, deadlock-freedom, and liveness.

Sources

Related papers