Interconnectability of session-based logical processes

Bernardo Toninho, Nobuko Yoshida

Research output: Contribution to journalArticle

1 Downloads (Pure)

Abstract

In multiparty session types, interconnection networks identify which roles in a session engage in communication (i.e., two roles are connected if they exchange a message). In session-based interpretations of linear logic the analogue notion corresponds to determining which processes are composed, or cut, using compatible channels typed by linear propositions. In this work, we show that well-formed interactions represented in a session-based interpretation of classical linear logic (CLL) form strictly less-expressive interconnection networks than those of a multiparty session calculus. To achieve this result, we introduce a new compositional synthesis property dubbed partial multiparty compatibility (PMC), enabling us to build a global type denoting the interactions obtained by iterated composition of well-typed CLL threads. We then show that CLL composition induces PMC global types without circular interconnections between three (or more) participants. PMC is then used to define a new CLL composition rule that can form circular interconnections but preserves the deadlock-freedom of CLL.

Original languageEnglish
Article number17
JournalACM Transactions on Programming Languages and Systems
Volume40
Issue number4
DOIs
Publication statusPublished - 1 Dec 2018

Keywords

  • Classical linear logic
  • Multiparty sessions
  • Session types
  • Synthesis

Fingerprint Dive into the research topics of 'Interconnectability of session-based logical processes'. Together they form a unique fingerprint.

Cite this