2018 - Technical Reports

Number Report Title
2018/1 Soundness of a Concurrent Collector for Actors
Juliana Franco, Sylvan Clebsch, Sophia Drossopoulou, Jan Vitek and Tobias Wrigstad, 42pp
2018/2 LibSEAL: Revealing Service Integrity Violations Using Trusted Execution
Pierre-Louis Aublin, Florian Kelbert, Dan O'Keeffe, Divya Muthukumaran, Christian Priebe, Joshua Lind, Robert Krahn, Christof Fetzer, David Eyers and Peter Pietzuch, 16pp
2018/3 A Concurrent Specification of POSIX File Systems
Gian Ntzik, Pedro da Rocha Pinto, Julian Sutherland and Philippa Gardner, 54pp
2018/4 Distributed Programming using Role-Parametric Session Types in Go
David Castro, Raymond Hu, Sung-Shik Jongmans, Nicholas Ng and Nobuko Yoshida, 220pp
2018/5 Two sides of the same coin: Session Types and Game Semantics
Simon Castellan and Nobuko Yoshida, 57pp
2018/6 Less is More: Multiparty Session Types Revisited
Alceste Scalas and Nobuko Yoshida, 71pp

Soundness of a Concurrent Collector for Actors

Juliana Franco, Sylvan Clebsch, Sophia Drossopoulou, Jan Vitek and Tobias Wrigstad, 42pp
Report: 2018/1

Download PDF Download

ORCA is a garbage collection protocol for actor-based programs. Multiple actors may mutate the heap while the collector is running without any dedicated synchronisation. ORCA is applicable to any actor language whose type system prevents data races and which supports causal message delivery. We present a model of ORCA which is parametric to the host language and its type system. We describe the interplay between the host language and the collector. We give invariants preserved by ORCA, and prove its soundness and completeness.


LibSEAL: Revealing Service Integrity Violations Using Trusted Execution

Pierre-Louis Aublin, Florian Kelbert, Dan O'Keeffe, Divya Muthukumaran, Christian Priebe, Joshua Lind, Robert Krahn, Christof Fetzer, David Eyers and Peter Pietzuch, 16pp
Report: 2018/2

Download PDF Download

Users of online services such as messaging, code hosting and collaborative document editing expect the services to uphold the integrity of their data. Despite providers' best efforts, data corruption still occurs, but at present service integrity violations are excluded from SLAs. For providers to include such violations as part of SLAs, the competing requirements of clients and providers must be satisfied. Clients need the ability to independently identify and prove service integrity violations to claim compensation. At the same time, providers must be able to refute spurious claims.


A Concurrent Specification of POSIX File Systems

Gian Ntzik, Pedro da Rocha Pinto, Julian Sutherland and Philippa Gardner, 54pp
Report: 2018/3

Download PDF Download

POSIX is a standard for operating systems, with a substantial part devoted to specifying file-system operations. File-system operations exhibit complex concurrent behaviour, comprising multiple actions affecting different parts of the state: typically, multiple atomic reads followed by an atomic update. However, the standard's description of concurrent behaviour is unsatisfactory: it is fragmented; contains ambiguities; and is generally under-specified. We provide a formal concurrent specification of POSIX file systems and demonstrate scalable reasoning for clients. Our specification is based on a concurrent specification language, which uses a modern concurrent separation logic for reasoning about abstract atomic operations, and an associated refinement calculus. Our reasoning about clients highlights an important difference between reasoning about modules built over a heap, where the interference on the shared state is restricted to the operations of the module, and modules built over a file system, where the interference cannot be restricted as the file system is a public namespace. We introduce specifications conditional on context invariants used to restrict the interference, and apply our reasoning to the example of lock files.


Distributed Programming using Role-Parametric Session Types in Go

David Castro, Raymond Hu, Sung-Shik Jongmans, Nicholas Ng and Nobuko Yoshida, 220pp
Report: 2018/4

Download PDF Download

This paper presents a framework for the static specification and safe programming of message passing protocols where the number and kinds of participants are dynamically instantiated. We develop the first theory of distributed multiparty session types (MPST) to support parameterised protocols with indexed roles - our framework statically infers the different kinds of participants induced by a protocol definition as role variants, and produces decoupled endpoint projections of the protocol onto each variant. This enables safe MPST-based programming of the parameterised endpoints in distributed settings: each endpoint can be implemented separately by different programmers, using different techniques (or languages). We prove the decidability of role variant inference and well-formedness checking, and the correctness of projection. We implement our theory as a toolchain for programming such role-parametric MPST protocols in Go. Our approach is to generate API families of lightweight, protocol- and variant-specific type wrappers for I/O. The APIs ensure a well-typed Go endpoint program (by native Go type checking) will perform only compliant I/O actions w.r.t. the source protocol. We leverage the abstractions of MPST to support the specification and implementation of Go applications involving multiple channels, possibly over mixed transports (e.g., Go channels, TCP), and channel passing via a unified programming interface. We evaluate the applicability and run-time performance of our generated APIs using microbenchmarks and real-world applications.


Two sides of the same coin: Session Types and Game Semantics

Simon Castellan and Nobuko Yoshida, 57pp
Report: 2018/5

Download PDF Download

Game semantics and session types are two formalisations of the same concept: message-passing open programs following certain protocols. Game semantics represents protocols as games, and programs as strategies; while session types specify protocols, and well-typed π-calculus processes model programs. Giving faithful models of the π-calculus and giving a precise description of strategies as a programming language are two difficult problems. In this paper, we show how these two problems can be tackled at the same time by building an accurate game semantics model of the session π-calculus. Our main contribution is to fill a semantic gap between the synchrony of the (session) π-calculus and the asynchrony of game semantics, by developing an event-structure based game semantics for synchronous concurrent computation. This model supports the first truly concurrent fully abstract (for barbed congruence) interpretation of the synchronous (session) π-calculus. We further strengthen this correspondence, establishing finite definability of asynchronous strategies by the internal session π-calculus. As an application of these results, we propose a faithful encoding of synchronous strategies into asynchronous strategies by call-return protocols, which induces automatically an encoding at the level of processes. Our results bring session types and game semantics into the same picture, proposing the session calculus as a programming language for strategies, and strategies as a very accurate model of the session calculus. We implement a prototype which computes the interpretation of session processes as synchronous strategies.


Less is More: Multiparty Session Types Revisited

Alceste Scalas and Nobuko Yoshida, 71pp
Report: 2018/6

Download PDF Download

Multiparty Session Types (MPST) are a typing discipline ensuring that a message-passing process implements without errors a given multiparty session protocol. In this paper, we propose a new, generalised MPST theory. Our contribution is fourfold.

1. We reveal that a revision of the theoretical foundations of MPST is necessary: classic MPST have a limited subject reduction property, with inherent restrictions that are easily overlooked, and in previous work have led to flawed type safety proofs; our new theory removes such restrictions and fixes such flaws.

2. We contribute a new MPST theory that is less complicated, and yet more general, than the classic one: it does not require global multiparty session types nor binary session type duality — instead, it is grounded on general behavioural type-level properties, and proves type safety of many more protocols and processes.

3. We produce a detailed analysis of type-level properties, showing how, in our new theory, they allow to ensure decidability of type checking, and statically guarantee that processes enjoy, e.g., deadlock-freedom and liveness at run-time.

4. We show how our new theory can integrate type and model checking: type-level properties can be expressed in modal μ-calculus, and verified with well-established tools.