MobilityReadingGroup

Multiparty Session Types as Coherence Proofs

Marco CARBONE , Fabrizio MONTESI , Carsten SCHÜRMANN , Nobuko YOSHIDA

We propose a Curry-Howard correspondence between a language for programming multiparty sessions and a generalisation of Classical Linear Logic (CLL). In this framework, propositions correspond to the local behaviour of a participant in a multiparty session type, proofs to processes, and proof normalisation to executing communications. Our key contribution is generalising duality, from CLL, to a new notion of n-ary compatibility, called coherence. Building on coherence as a principle of compositionality, we generalise the cut rule of CLL to a new rule for composing many processes communicating in a multiparty session. We prove the soundness of our model by showing the admissibility of our new rule, which entails deadlock-freedom via our correspondence.

@inproceedings{CMSY2015,
  author = {Marco Carbone and Fabrizio Montesi and Carsten Schürmann and Nobuko Yoshida},
  title = {{Multiparty Session Types as Coherence Proofs}},
  booktitle = {26th International Conference on Concurrency Theory},
  series = {LIPIcs},
  volume = {42},
  pages = {412--426},
  publisher = {Schloss Dagstuhl},
  year = 2015
}

@inproceedings{CMSY2015,
  author = {Marco Carbone and Fabrizio Montesi and Carsten Schürmann and Nobuko Yoshida},
  title = {{Multiparty Session Types as Coherence Proofs}},
  booktitle = {26th International Conference on Concurrency Theory},
  series = {LIPIcs},
  volume = {42},
  pages = {412--426},
  publisher = {Schloss Dagstuhl},
  doi = "10.4230/LIPIcs.CONCUR.2015.412",
  year = 2015
}