POPL 2027
Sun 10 - Sat 16 January 2027 Mexico City, Mexico

Session types provide a formal system for modeling and verifying message-passing concurrent systems. When constructed based on linear logic, they provide powerful guarantees of deadlock freedom and lack of data races, along with type preservation preventing communication errors. Unfortunately, these strong guarantees also require a major restriction that channels be treated strictly linearly, which precludes any form of sharing and significantly restricts the expressiveness of the resulting language. This work aims to relax this restriction by exploring a notion of immutability in message-passing. Intuitively, we introduce type-level constructors that demarcate an immutable operation, allowing for temporary state changes but requiring that state is restored at the end of the operation. To accommodate this notion of immutability, we introduce FracST, a novel type system based on a system of borrowing and fractional permissions that tracks whether a process holds a mutable or immutable reference to a channel. Our type system resembles Rust’s `Aliasing XOR Mutability’ property: a channel can either have a single mutable reference or several immutable references. This enables safe sharing of channels between multiple clients without introducing the possibility of deadlocks, data races, or communication errors, proven via standard type safety theorems of progress and preservation. We implement FracST to demonstrate the efficacy of the language on real world examples, including shared data structures like queues, binary trees, and AVL trees, and protocols like an auction and MapReduce.