Search papers, labs, and topics across Lattice.
This paper establishes a precise subtyping relation for mixed choice multiparty session types, ensuring that a program of subtype \( T' \) can safely replace a program of type \( T \) without compromising safety. The authors develop the first comprehensive type system for a mixed choice multiparty session \(\pi\)-calculus and introduce a novel proof technique utilizing scheduler processes to detect failures in the subtyping relation. Their algorithms for checking subtyping, safety, deadlock-freedom, and liveness are optimized to run in quadratic time, demonstrating effectiveness through case studies.
A new proof technique reveals how to exhaustively detect subtyping failures in multiparty session types, enhancing program safety guarantees.
A precise (sound and complete) subtyping relation $\leq$ specifies that $T'$ is a subtype of $T$ if and only if a program of type $T'$ can always safely replace a program of type $T$ without compromising the safety of a larger program. This paper formulates and proves preciseness of subtyping for mixed choice multiparty session types with session delegation, creation, and interleaving. We prove soundness by developing the first general type system for a full mixed choice multiparty session $\pi$-calculus. To prove completeness, we introduce the three-party lock, which is a minimal and general form of liveness error for handling interleaved sessions, and we establish a new proof technique based on a construction of scheduler processes which enable exhaustive detection for all failures of the subtyping relation. We then extend the preciseness results to a family of mixed choice multiparty session types. Algorithms for checking (1) subtyping and (2) safety, deadlock-freedom, and liveness of typing contexts are fully implemented and optimised to run in quadratic time with respect to the size of the state space and typing context, and have been evaluated with (mixed choice) case studies from the literature.
