Separation and Encodability in Mixed Choice Multiparty Sessions
Article No.: 62, Pages 1 - 15
Abstract
Multiparty session types (MP) are a type discipline for enforcing the structured, deadlock-free communication of concurrent and message-passing programs. Traditional MP have a limited form of choice in which alternative communication possibilities are offered by a single participant and selected by another. Mixed choice multiparty session types (MCMP) extend the choice construct to include both selections and offers in the same choice. This paper first proposes a general typing system for a mixed choice synchronous multiparty session calculus, and prove type soundness, communication safety, and deadlock-freedom.
Next we compare expressiveness of nine subcalcli of MCMP-calculus by examining their encodability (there exists a good encoding from one to another) and separation (there exists no good encoding from one calculus to another). We prove 8 new encodablity results and 20 new separation results. In summary, MCMP is strictly more expressive than classical multiparty sessions (MP) in [19] and mixed choice in mixed sessions in [8]. This contrasts to the results proven in [8, 50] where mixed sessions [8] do not add any expressiveness to non-mixed fundamental sessions in [64], shedding a light on expressiveness of multiparty mixed choice.
References
[1]
Adam D. Barwell, Alceste Scalas, Nobuko Yoshida, and Fangyi Zhou. 2022. Generalised Multiparty Session Types with Crash-Stop Failures. In 33rd International Conference on Concurrency Theory (LIPIcs, Vol. 243). Dagstuhl, 35:1--35:25.
[2]
Romain Beauxis, Catuscia Palamidessi, and Frank D. Valencia. 2008. On the Asynchronous Nature of the Asynchronous pi-Calculus. In Concurrency, Graphs and Models (LNCS, Vol. 5065). Springer, 473--492.
[3]
Gérard Berry and Georges Gonthier. 1992. The Esterel synchronous programming language: design, semantics, implementation. Science of Computer Programming 19, 2 (1992), 87--152.
[4]
Gérard Boudol. 1992. Asynchrony and the π-calculus (note). Technical Report. Rapport de Recherche 1702, INRIA, Sophia-Antipolis.
[5]
Daniel Brand and Pitro Zafiropulo. 1983. On Communicating Finite-State Machines. J. ACM 30, 2 (apr 1983), 323--342.
[6]
Marco Carbone, Kohei Honda, and Nobuko Yoshida. 2007. Structured Communication-Centred Programming for Web Services. In Proceedings of ESOP 2007 (LNCS, Vol. 4421). Springer, 2--17.
[7]
Luca Cardelli and Andrew D. Gordon. 2000. Mobile Ambients. Theoretical Computer Science 240, 1 (2000), 177--213. Special Issue on Coordination, D. Le Métayer Editor.
[8]
Filipe Casal, Andreia Mordido, and Vasco T. Vasconcelos. 2022. Mixed sessions. Theoretical Computer Science 897 (2022), 23--48.
[9]
Giuseppe Castagna, Mariangiola Dezani-Ciancaglini, and Luca Padovani. 2012. On Global Types and Multi-Party Session. Logical Methods in Computer Science 8, 1 (2012).
[10]
Sagar Chaki, Sriram K. Rajamani, and Jakob Rehof. 2002. Types as Models: Model Checking Message-Passing Programs. In Proceedings of the 29th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (Portland, Oregon) (POPL '02). Association for Computing Machinery, New York, NY, USA, 45--57.
[11]
Tzu-Chun Chen, Mariangiola Dezani-Ciancaglini, Alceste Scalas, and Nobuko Yoshida. 2017. On the Preciseness of Subtyping in Session Types. Logical Methods in Computer Science 13, 2 (2017).
[12]
Mario Coppo, Mariangiola Dezani-Ciancaglini, Luca Padovani, and Nobuko Yoshida. 2015. A Gentle Introduction to Multiparty Asynchronous Session Types. In 15th International School on Formal Methods for the Design of Computer, Communication and Software Systems: Multicore Programming (LNCS, Vol. 9104). Springer, 146--178.
[13]
Luís Cruz-Filipe, Fabrizio Montesi, and Marco Peressotti. 2018. Communications in Choreographies, Revisited. In Proceedings of the 33rd Annual ACM Symposium on Applied Computing. 1248--1255.
[14]
Romain Demangeon and Kohei Honda. 2011. Full Abstraction in a Subtyped pi-Calculus with Linear Types. In Proceedings of CONCUR 2011 (LNCS, Vol. 6901). Springer, 280--296.
[15]
Cédric Fournet and Georges Gonthier. 1996. The Reflexive Chemical Abstract Machine and the Join-Calculus. In Proc. of POPL, Jr. Guy Steele (Ed.). ACM, 372--385.
[16]
Yuxi Fu. 2016. Theory of Interaction. Theoretical Computer Science 611 (2016), 1--49.
[17]
Yuxi Fu and Hao Lu. 2010. On the expressiveness of interaction. Theor. Comput. Sci. 411, 11-13 (2010), 1387--1451.
[18]
Julia Gabet and Nobuko Yoshida. 2020. Static Race Detection and Mutex Safety and Liveness for Go Programs. In 34th European Conference on Object-Oriented Programming (LIPIcs). Schloss Dagstuhl.
[19]
Silvia Ghilezan, Svetlana Jaksic, Jovanka Pantovic, Alceste Scalas, and Nobuko Yoshida. 2019. Precise subtyping for synchronous multiparty sessions. Journal of Logical and Algebraic Methods in Programming 104 (2019), 127--173.
[20]
Silvia Ghilezan, Jovanka Pantovic, Ivan Prokic, Alceste Scalas, and Nobuko Yoshida. 2021. Precise Subtyping for Asynchronous Multiparty Sessions. In Proceedings of the ACM on Programming Languages (POPL, Vol. 5). ACM, 16:1--16:28.
[21]
Jean-Yves Girard. 1987. Linear Logic. TCS 50 (1987), 1--102.
[22]
Go Language. 2023. The Go Programming Language homepage. www.go.dev.
[23]
Daniele Gorla. 2009. On the Relative Expressive Power of Calculi for Mobility. In Proc. of MFPS (ENTCS, Vol. 249). 269--286.
[24]
Daniele Gorla. 2010. Towards a unified approach to encodability and separation results for process calculi. Inf. Comput. 208, 9 (2010), 1031--1053.
[25]
Ruben Hamers and Sung-Shik Jongmans. 2020. Discourje: Runtime Verification of Communication Protocols in Clojure. In Tools and Algorithms for the Construction and Analysis of Systems, Armin Biere and David Parker (Eds.). Springer International Publishing, Cham, 266--284.
[26]
Kohei Honda. 1993. Types for Dyadic Interaction. In CONCUR'93 (LNCS, Vol. 715), Eike Best (Ed.). Springer-Verlag, 509--523.
[27]
Kohei Honda and Mario Tokoro. 1991. An Object Calculus for Asynchronous Communication. In Proceedings of ECOOP 1991 (LNCS, Vol. 512). Springer, 133--147.
[28]
Kohei Honda, Vasco T. Vasconcelos, and Makoto Kubo. 1998. Language Primitives and Type Disciplines for Structured Communication-based Programming. In Proceedings of ESOP 1998 (LNCS, Vol. 1381). Springer, 22--138.
[29]
Kohei Honda, Nobuko Yoshida, and Marco Carbone. 2008. Multiparty Asynchronous Session Types. In Proceedings of POPL 2008. ACM, 273--284.
[30]
Kohei Honda, Nobuko Yoshida, and Marco Carbone. 2016. Multiparty Asynchronous Session Types. Journal of the ACM 63, 1 (2016), 9:1--9:67.
[31]
Sung-Shik Jongmans and Francisco Ferreira. 2023. Synthetic Behavioural Typing: Sound, Regular Multiparty Sessions via Implicit Local Types. In 37th European Conference on Object-Oriented Programming (ECOOP 2023) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 263), Karim Ali and Guido Salvaneschi (Eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 42:1--42:30.
[32]
Sung-Shik Jongmans and Nobuko Yoshida. 2020. Exploring Type-Level Bisimilarity towards More Expressive Multiparty Session Types. In 29th European Symposium on Programming (LNCS, Vol. 12075). Springer, 251--279.
[33]
Julien Lange, Nicholas Ng, Bernardo Toninho, and Nobuko Yoshida. 2018. A static verification framework for message passing in Go using behavioural types. In Proceedings of ICSE 2018. ACM, 1137--1148.
[34]
Elaine Li, Felix Stutz, Thomas Wies, and Damien Zufferey. 2023. Complete Multiparty Session Type Projection with Automata. In Computer Aided Verification, Constantin Enea and Akash Lal (Eds.). Springer Nature Switzerland, 350--373.
[35]
Rupak Majumdar, Madhavan Mukund, Felix Stutz, and Damien Zufferey. 2021. Generalising Projection in Asynchronous Multiparty Session Types. In 32nd International Conference on Concurrency Theory, CONCUR 2021, August 24-27, 2021, Virtual Conference (LIPIcs, Vol. 203), Serge Haddad and Daniele Varacca (Eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 35:1--35:24.
[36]
Robin Milner. 1989. Communication and Concurrency. Prentice-Hall, Inc., USA.
[37]
Robin Milner. 1991. The Polyadic pi-calculus: A Tutorial. LFCS, Department of Computer Science, University of Edinburgh. https://books.google.co.uk/books?id=ht-9PQAACAAJ
[38]
Robin Milner, Joachim Parrow, and David Walker. 1992. A Calculus of Mobile Processes, Parts I and II.
[39]
Robin Milner and Davide Sangiorgi. 1992. Barbed Bisimulation. In Proc. of ICALP (LNCS, Vol. 623). 685--695.
[40]
Uwe Nestmann. 2000. What is a "Good" Encoding of Guarded Choice? Information and Computation 156, 1-2 (2000), 287--319.
[41]
Catuscia Palamidessi. 2003. Comparing The Expressive Power Of The Synchronous And Asynchronous Pi-Calculi. Mathematical Structures in Computer Science 13, 5 (2003), 685--719.
[42]
Joachim Parrow. 2008. Expressiveness of Process Algebras. Electr. Notes Theor. Comput. Sci. 209 (2008), 173--186.
[43]
Kirstin Peters. 2012. Translational Expressiveness. Ph. D. Dissertation. TU Berlin. http://opus.kobv.de/tuberlin/volltexte/2012/3749/
[44]
Kirstin Peters. 2019. Comparing Process Calculi Using Encodings. In Proc. of EXPRESS/SOS (EPTCS). 19--38.
[45]
Kirstin Peters and Uwe Nestmann. 2012. Is It a "Good" Encoding of Mixed Choice?. In Foundations of Software Science and Computational Structures - 15th International Conference, FOSSACS 2012, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2012, Tallinn, Estonia, March 24 - April 1, 2012. Proceedings (Lecture Notes in Computer Science, Vol. 7213), Lars Birkedal (Ed.). Springer, 210--224.
[46]
Kirstin Peters and Uwe Nestmann. 2020. Distributability of Mobile Ambients. Information and Computation 275 (2020), 104608.
[47]
Kirstin Peters, Uwe Nestmann, and Ursula Goltz. 2013. On Distributability in Process Calculi. In Proc. of ESOP 2013 (LNCS, Vol. 7792). Springer, 310--329.
[48]
Kirstin Peters, Jens-Wolfhard Schicke-Uffmann, and Uwe Nestmann. 2011. Synchrony vs Causality in the Asynchronous Pi-Calculus. In Proc. of EXPRESS (EPTCS, Vol. 64). 89--103.
[49]
Kirstin Peters and Rob J. van Glabbeek. 2015. Analysing and Comparing Encodability Criteria. In Proc. of EXPRESS/SOS 2015 (EPTCS, Vol. 190). 46--60.
[50]
Kirstin Peters and Nobuko Yoshida. 2022. On Expressiveness of Mixed Choice Sessions. EPTCS 368 (2022), 113--130.
[51]
Kirstin Peters and Nobuko Yoshida. 2024. Separation and Encodability in Mixed Choice Multiparty Sessions (Technical Report). arXiv:2405.08104 [cs.LO]
[52]
John Reppy, Claudio V. Russo, and Yingqi Xiao. 2009. Parallel Concurrent ML. SIGPLAN Not. 44, 9 (aug 2009), 257--268.
[53]
John H. Reppy. 1991. CML: A Higher-Order Concurrent Language. In PLDI. 293--305.
[54]
Alceste Scalas and Nobuko Yoshida. 2018. Less is More: Multiparty Session Types Revisited. DoC Technical Report DTRS-18-6. Imperial College London.
[55]
Alceste Scalas and Nobuko Yoshida. 2019. Less is More: Multiparty Session Types Revisited. Proc. ACM Program. Lang. 3, POPL, Article 30 (Jan. 2019), 29 pages.
[56]
Alceste Scalas, Nobuko Yoshida, and Elias Benussi. 2019. Verifying Message-Passing Programs with Dependent Behavioural Types. In Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation (Phoenix, AZ, USA) (PLDI 2019). Association for Computing Machinery, New York, NY, USA, 502--516.
[57]
Kaku Takeuchi, Kohei Honda, and Makoto Kubo. 1994. An Interaction-based Language and its Typing System. In PARLE'94 (LNCS, Vol. 817). 398--413.
[58]
Bent Thomsen, Lone Leth, and Tsung-Min Kuo. 1996. A Facile tutorial. In CONCUR '96: Concurrency Theory, Ugo Montanari and Vladimiro Sassone (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 278--298.
[59]
Rob van Glabbeek. 2018. A Theory of Encodings and Expressiveness (Extended Abstract). In Proc. of FoSSaCS (LNCS, Vol. 10803). 183--202.
[60]
Rob van Glabbeek, Ursula Goltz, and Jens-Wolfhard Schicke. 2008. On Synchronous and Asynchronous Interaction in Distributed Systems. In Proc. of MFCS (LNCS, Vol. 5162). 16--35.
[61]
Rob van Glabbeek, Ursula Goltz, and Jens-Wolfhard Schicke-Uffmann. 2012. On Distributability of Petri Nets. In Proc. of FoSSaCS (LNCS, Vol. 7213). 331--345.
[62]
Rob J. van Glabbeek. 2012. Musings on Encodings and Expressiveness. In Proc. of EXPRESS/SOS 2012 (EPTCS, Vol. 89). 81--98.
[63]
Rob J. van Glabbeek. 2022. Comparing the expressiveness of the π-calculus and CCS. In Proc. of ETAPS (LNCS, Vol. 13240), Ilya Sergey (Ed.). Springer, 548--574.
[64]
Vasco T. Vasconcelos. 2012. Fundamentals of session types. Information and Computation 217 (2012), 52--70.
[65]
Nobuko Yoshida and Lorenzo Gheri. 2020. A Very Gentle Introduction to Multiparty Session Types. In 16th International Conference on Distributed Computing and Internet Technology (LNCS, Vol. 11969). Springer, 73--93.
[66]
Nobuko Yoshida and Ping Hou. 2024. Less is More Revisit. arXiv:2402.16741 [cs.PL] Accepted by Cliff B. Jones Festschrift Proceeding.
[67]
Nobuko Yoshida and Vasco Thudichum Vasconcelos. 2007. Language Primitives and Type Discipline for Structured Communication-Based Programming Revisited: Two Systems for Higher-Order Session Communication. Electr. Notes Theor. Comput. Sci. 171, 4 (2007), 73--93.
Index Terms
- Separation and Encodability in Mixed Choice Multiparty Sessions
Recommendations
Precise Subtyping for Asynchronous Multiparty Sessions
Session subtyping is a cornerstone of refinement of communicating processes: A process implementing a session type (i.e., a communication protocol) T can be safely used whenever a process implementing one of its supertypes T′ is expected, in any context, ...
Mixed Sessions
Programming Languages and SystemsAbstractSession types describe patterns of interaction on communicating channels. Traditional session types include a form of choice whereby servers offer a collection of options, of which each client picks exactly one. This sort of choice constitutes a ...
Mixed sessions
AbstractSession types describe patterns of interaction on communicating channels. Traditional session types include a form of choice whereby servers offer a collection of options, of which each client selects exactly one. Mixed choices blur ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2024
988 pages
ISBN:9798400706608
DOI:10.1145/3661814
- Conference Chair:
- Pawel Sobocinski,
- Program Chairs:
- Ugo Dal Lago,
- Javier Esparza
This work is licensed under a Creative Commons Attribution International 4.0 License.
Sponsors
- SIGLOG: ACM Special Interest Group on Logic and Computation
- IEEE Computer Society
In-Cooperation
- EACSL
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 08 July 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
Conference
LICS '24
Sponsor:
LICS '24: 39th Annual ACM/IEEE Symposium on Logic in Computer Science
July 8 - 11, 2024
Tallinn, Estonia
Acceptance Rates
LICS '24 Paper Acceptance Rate 72 of 236 submissions, 31%;
Overall Acceptance Rate 215 of 622 submissions, 35%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 80Total Downloads
- Downloads (Last 12 months)80
- Downloads (Last 6 weeks)15
Reflects downloads up to 03 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in