Multiparty Asynchronous Session Types: A Mechanised Proof of Subject Reduction
Session types offer a type-based approach to describing the message exchange protocols between participants in communication-based systems. % Initially, they were introduced in a binary setting, specifying communication patterns between two components. With the advent of multiparty session types (MPST), the typing discipline was extended to arbitrarily many components. In MPST, communication patterns are given in terms of global types, an Alice-Bob notation that gives a global view of how components interact. A central theorem of MPST is subject reduction: a well-typed system remains well-typed after reduction. The literature contains formulations of MPST with proofs of subject reduction that have later been shown to be incorrect. In this paper, we show that the subject reduction proof of the original formulation of MPST by Honda et al. contains some flaws. % Additionally, we provide a restriction to the theory and show that, for this fragment, subject reduction does indeed hold. Finally, we use subject reduction to show that well-typed processes never go wrong. All of our proofs are mechanised using the Coq proof assistant.
Mon 30 JunDisplayed time zone: Amsterdam, Berlin, Bern, Rome, Stockholm, Vienna change
14:00 - 15:45 | Concurrency and TypesTechnical Papers at Auditorium M003 Chair(s): João Costa Seco NOVA-LINCS; Nova University of Lisbon | ||
14:00 21mTalk | Contrasting Deadlock-Free Session Processes Technical Papers DOI | ||
14:21 21mTalk | Fair Termination of Asynchronous Binary Sessions Technical Papers Luca Padovani Department of Computer Science and Engineering - Università di Bologna, Gianluigi Zavattaro Department of Computer Science and Engineering - Università di Bologna | ||
14:42 21mTalk | Incremental Computing by Differential Execution Technical Papers | ||
15:03 21mTalk | Multiparty Asynchronous Session Types: A Mechanised Proof of Subject Reduction Technical Papers Dawit Tirore IT University of Copenhagen, Denmark, Jesper Bengtson IT University of Copenhagen, Marco Carbone IT University of Copenhagen | ||
15:24 21mTalk | Validating Persistency Semantics with Memory Hierarchy Timing Attack Technical Papers Vasileios Klimis Queen Mary University of London |