论文库

原文摘要

Distributed systems increasingly rely on randomisation; yet, verification techniques for such systems remain separate from the programming abstractions used to build them. This paper proposes the first probabilistic extension of general multiparty session types - typing sessions bottom-up, with no global specification - deriving quantitative properties of a multiparty session from its session types alone. Our types combine probabilistic choice with nondeterministic choice that abstracts data-dependent control, and allow separated choices, where each branch of a selection or branching may involve a different participant - a combination beyond previous probabilistic multiparty session type systems. To achieve this, we develop a novel probabilistic subtyping relation and merge operator, using which we prove type soundness and session fidelity. The semantics of typing contexts separates nondeterministic resolution, probabilistic choice, and synchronisation, so that every typing context induces a finite Markov decision process. On it, we derive sound lower bounds, holding under every fair adversarial scheduler, on the probability that a session is deadlock-free and live - the first behavioural property guarantees, partial or otherwise, for a probabilistic session calculus. To connect session types with probabilistic model checking, we introduce the first translation from session types into the PRISM modelling language, and prove it sound and complete with respect to our operational semantics. We implement the framework in the toolchain Prose, which translates probabilistic multiparty session typing contexts into PRISM and checks safety, deadlock-freedom, and liveness.