Multiparty Session Types as Coherence Proofs

Marco Carbone, Fabrizio Montesi, Carsten Schürmann, Nobuko Yoshida [2015].
In proceedings of CONCUR 2015, pp. 412-426.

Abstract

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.

Links

doi.org

Additional notes

None

Cite (BibTeX)

Click to expand

@inproceedings{DBLP:conf/concur/CarboneMSY15,
  author       = {Marco Carbone and
                  Fabrizio Montesi and
                  Carsten Sch{\"{u}}rmann and
                  Nobuko Yoshida},
  editor       = {Luca Aceto and
                  David de Frutos{-}Escrig},
  title        = {Multiparty Session Types as Coherence Proofs},
  booktitle    = {26th International Conference on Concurrency Theory, {CONCUR} 2015,
                  Madrid, Spain, September 1.4, 2015},
  series       = {LIPIcs},
  volume       = {42},
  pages        = {412--426},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year         = {2015},
  url          = {https://doi.org/10.4230/LIPIcs.CONCUR.2015.412},
  doi          = {10.4230/LIPIcs.CONCUR.2015.412},
  timestamp    = {Fri, 27 Mar 2020 08:51:56 +0100},
  biburl       = {https://dblp.org/rec/conf/concur/CarboneMSY15.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

A PDF is available (possibly a preprint):

Some data from DBLP and Crossref.