MobilityReadingGroup

Formalising Subject Reduction and Progress for Multiparty Session Processes

Burak EKICI , Tadayoshi KAMEGAI , Nobuko YOSHIDA

Multiparty session types (MPST) provide a robust typing discipline for specifying and verifying communication protocols in concurrent and distributed systems involving multiple participants. This work formalises the non-stuck theorem for synchronous MPST in the Coq proof assistant, ensuring that well-typed communications never get stuck. We present a fully mechanised proof of the theorem, where recursive type unfoldings are modelled as infinite trees, leveraging coinductive reasoning. This marks the first formal proof to incorporate precise subtyping, aiming to extend the typability of processes thus precision of the type system. The proof is grounded in fundamental properties such as subject reduction and progress. During the mechanisation process, we discovered that the structural congruence rule for recursive processes, as presented in several prior works on MPST, violates subject reduction. We resolve this issue by revising and formalising the rule to ensure the preservation of type soundness. Our approach to formal proofs about infinite type trees involves analysing their finite prefixes through inductive reasoning within outer-level coinductively stated goals. We employ the greatest fixed point of the parameterised least fixed point technique to define coinductive predicates and use parameterised coinduction to prove properties. The formalisation comprises approximately 16K lines of Coq code, accessible at: https://github.com/Apiros3/smpst-sr-smer.

@inproceedings{EKY2025,
  author = {Burak Ekici and Tadayoshi Kamegai and Nobuko Yoshida},
  title = {{Formalising Subject Reduction and Progress for Multiparty Session Processes}},
  booktitle = {16th International Conference on Interactive Theorem Proving, 2025, Reykjavik, Iceland},
  pages = {--},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{"{u}}r Informatik},
  year = 2025
}

@inproceedings{EKY2025,
  author = {Burak Ekici and Tadayoshi Kamegai and Nobuko Yoshida},
  title = {{Formalising Subject Reduction and Progress for Multiparty Session Processes}},
  booktitle = {16th International Conference on Interactive Theorem Proving, 2025, Reykjavik, Iceland},
  pages = {--},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{"{u}}r Informatik},
  year = 2025
}