paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Less is more: multiparty session types revisited

少即是多:多方会话类型再探
POPL 3(POPL)2019匹配度 2/10 · 该论文属于并发会话类型与形式化验证的理论工作,虽与程序语言和形式方法相关,但未涉及用户核心关注的 LLM/Agent 与静态分析/形式验证交叉、浮点程序分析或贝叶斯程序分析。引用 104 inbox
Alceste Scalas, Nobuko Yoshida
crossref: 2026-09-10

AI 速览

一句话:提出更简单且更通用的多方会话类型理论,去除全局类型与二元对偶,修复类型安全证明缺陷,并支持可判定类型检查与活性保证。

经典多方会话类型(MPST)用类型保证消息传递进程正确实现多方会话协议,但其理论基础存在严重局限:主题归约性质受限,隐含限制容易被忽略,已有工作甚至因此出现类型安全证明缺陷。本文重新审视 MPST,提出一个更简单却更通用的理论:它不要求全局多方会话类型,也不依赖二元会话类型对偶,而是基于一般行为类型级性质,从而能证明更多协议和进程的类型安全。作者进一步分析这些类型级性质,说明它们如何保证类型检查可判定,并静态确保运行时无死锁与活性。最后展示新理论可整合类型与模型检查,将类型级性质表达为模态 μ 演算,并用成熟工具验证。

问题
经典 MPST 的主题归约性质受限,隐含限制容易被忽视,且已有类型安全证明存在缺陷;同时其依赖全局会话类型和二元对偶,导致理论复杂且适用范围受限。
方法
作者提出新的通用 MPST 理论,去除全局多方会话类型与二元会话类型对偶,转而基于一般行为类型级性质证明类型安全,并分析这些性质以保证类型检查可判定、静态确保运行时无死锁与活性。
评估
论文以理论分析与性质刻画论证新理论更简单、更通用并修复旧缺陷;还展示可将类型级性质编码为模态 μ 演算,并借助现有模型检查工具进行验证。
原文摘要(Abstract)

Multiparty Session Types (MPST) are a typing discipline ensuring that a message-passing process implements a multiparty session protocol , without errors. In this paper, we propose a new, generalised MPST theory. Our contribution is fourfold. (1) We demonstrate that a revision of the theoretical foundations of MPST is necessary : classic MPST have a limited subject reduction property, with inherent restrictions that are easily overlooked, and in previous work have led to flawed type safety proofs; our new theory removes such restrictions and fixes such flaws. (2) We contribute a new MPST theory that is less complicated, and yet more general, than the classic one: it does not require global multiparty session types nor binary session type duality — instead, it is grounded on general behavioural type-level properties, and proves type safety of many more protocols and processes. (3) We produce a detailed analysis of type-level properties, showing how, in our new theory, they allow to ensure decidability of type checking, and statically guarantee that processes enjoy, , deadlock-freedom and liveness at run-time. (4) We show how our new theory can integrate type and model checking: type-level properties can be expressed in modal µ-calculus, and verified with well-established tools.

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@article{paperbot624,
  title = {Less is more: multiparty session types revisited},
  author = {Alceste Scalas and Nobuko Yoshida},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {3},
  number = {POPL},
  year = {2019},
  doi = {10.1145/3290343}
}