  Session types guarantee that message-passing processes adhere to predefined
communication protocols. Prior work on session types has focused on
deterministic languages but many message-passing systems, such as Markov chains
and randomized distributed algorithms, are probabilistic. To model and analyze
such systems, this article introduces probabilistic session types and explores
their application in automatic expected resource analysis. Probabilistic
session types describe probability distributions over messages and are a
conservative extension of intuitionistic (binary) session types. To send on a
probabilistic channel, processes have to utilize internal randomness from a
probabilistic branching expression or external randomness from receiving on a
probabilistic channel. The analysis for expected resource bounds is integrated
with the type system and is a variant of automatic amortized resource analysis.
It can automatically derive symbolic bounds for different cost metrics by
reducing type inference to linear constraint solving. The technical
contributions include the meta theory that is based on a novel nested
multiverse semantics and a type-reconstruction algorithm that allows flexible
mixing of different sources of randomness without burdening the programmer with
type annotations. The type system has been implemented in the language PRast.
Experiments demonstrate that PRast is applicable in different domains such as
resource analysis of randomized distributed algorithms, verification of
limiting distributions in Markov chains, and analysis of probabilistic digital
contracts.
