MobilityReadingGroup

π-calculus, Session Types research at Imperial College

Talks & Presentations

Recent invited talks and presentations from our group.

More recent
Understanding concurrency with behavioural types
GolangUK 2017, 16-18 Aug 2017

Concurrent programming is difficult. This talk is about applying programming languages & concurrency research, specifically behavioural types as an abstraction, to verify concurrent Go programs. The talk covers what behavioural types are and how they can be used to reason in Go’s concurrency model.

Date 16 Aug 2017 - 18 Aug 2017
Speakers
Let it Recover: Multiparty Protocol-Induced Recovery
Open Problems in Concurrency Theory II, Institute of Science of Technology Austria (IST Austria), Vienna
Date 26 Jun 2017 - 29 Jun 2017
Speakers
Open problems in session types
Open Problems in Concurrency Theory II, Institute of Science of Technology Austria (IST Austria), Vienna
Date 26 Jun 2017 - 29 Jun 2017
Speakers
Behavioural Type-Based Static Verification Framework for Go
HKU PL Group, The University of Hong Kong, Hong Kong, June 2017

Go is a production-level statically typed programming language whose design features explicit message-passing primitives and lightweight threads, enabling (and encouraging) programmers to develop concurrent systems where components interact through communication more so than by lock-based shared memory concurrency. Go can detect global deadlocks at runtime, but does not provide any compile-time protection against all too common communication mismatches and partial deadlocks.

In this work we present a static verification framework for liveness and safety in Go programs, able to detect communication errors and deadlocks by model checking. Our toolchain infers from a Go program a faithful representation of its communication patterns as behavioural types, where the types are model checked for liveness and safety.

This is joint work with Julien Lange, Bernardo Toninho, and Nobuko Yoshida.

Date 9 Jun 2017
Speakers
Behavioural Type-Based Static Verification Framework for Go
South of England Regional Programming Language Seminar, Department of Computer Science, UCL, May 2017

Go is a production-level statically typed programming language whose design features explicit message-passing primitives and lightweight threads, enabling (and encouraging) programmers to develop concurrent systems where components interact through communication more so than by lock-based shared memory concurrency. Go can detect global deadlocks at runtime, but does not provide any compile-time protection against all too common communication mismatches and partial deadlocks.

In this work we present a static verification framework for liveness and safety in Go programs, able to detect communication errors and deadlocks by model checking. Our toolchain infers from a Go program a faithful representation of its communication patterns as behavioural types, where the types are model checked for liveness and safety.

This is joint work with Julien Lange, Bernardo Toninho, and Nobuko Yoshida.

Date 25 May 2017
Speakers
Lightweight Session Programming in Scala
South of England Regional Programming Language Seminar, Department of Computer Science, UCL, May 2017

Designing, developing and maintaining concurrent applications is an error-prone and time-consuming task; most difficulties arise because compilers are usually unable to check whether the inputs/outputs performed by a program at runtime will adhere to a given protocol specification. To address this problem, we leverage the native features of the Scala programming language, type system and standard library, to introduce (1) a representation of protocols (session types) as Scala types, and (2) a library, called lchannels, with a convenient API for type-safe protocol-based programming, supporting local and distributed communication.

Date 25 May 2017
Speakers
Building Graphical Choreographies From Communicating Machines: Principles and Applications
FoSS group seminar, University of Sussex, May 2017

Graphical choreographies, or global graphs, are general multiparty session specifications featuring expressive constructs such as forking, merging, and joining for representing application-level protocols. Global graphs can be directly translated into modelling notations such as BPMN and UML. In the first part of the talk, I will first present an algorithm whereby a global graph can be constructed from asynchronous interactions represented by communicating finite-state machines (CFSMs); and a sound characterisation of a subset of safe CFSMs from which global graphs can be constructed. In the second part, I will outline a few recent applications of this work to communicating timed automata and the

Date 3 May 2017
Speakers
Lightweight Session Programming in Scala
Center for Mathematics and Statistics, University of Novi Sad, Serbia, March 2017

In this talk, we first outline recent activities in our mobility group in Department of Computing, Imperial College London. Then we talk about the following work on protocols and Scala.

Designing, developing and maintaining concurrent applications is an error-prone and time-consuming task; most difficulties arise because compilers are usually unable to check whether the inputs/outputs performed by a program at runtime will adhere to a given protocol specification. To address this problem, we leverage the native features of the Scala programming language, type system and standard library, to introduce (1) a representation of protocols (session types) as Scala types, and (2) a library, called lchannels, with a convenient API for type-safe protocol-based programming, supporting local and distributed communication.

During the talk, we will briefly illustrate the theoretical basis of our approach (starting from the representation of protocols as session types), provide a quick introduction to Scala, and show a demo of the lchannels library.

Date 27 Mar 2017
Speakers
Let It Recover: Multiparty Protocol-Induced Recovery
PLAS Group Seminar, School of Computing, University of Kent, UK

In this talk, first we summarise the recent activities on session types in Imperial College London http://mrg.doc.ic.ac.uk/.

Then we talk about a new recovery strategy in Erlang based on Multiparty session types, which was presented in 26th ACM International Conference on Compiler Construction (CC’17).

Fault-tolerant communication systems rely on recovery strategies which are often error-prone (e.g. a programmer manually specifies recovery strategies) or inefficient (e.g. the whole system is restarted from the beginning). In this talk, we will present an algorithm to efficiently compute a safe global state from which a system of interacting processes should be recovered. We statically analyse the communication flow of a program, given as a multiparty protocol, to extract the causal dependencies between processes and to localise failures. We formalise our recovery algorithm and prove its safety. A recovered communication system is free from deadlocks, orphan messages and reception errors. Our recovery algorithm incurs less communication cost (only affected processes are notified) and overall execution time (only required states are repeated). On top of our analysis, we design and implement a runtime framework in Erlang where failed processes and their dependencies are soundly restarted from a computed safe state. We evaluate our recovery framework on message-passing benchmarks and a use case for crawling web pages. The experimental results indicate our framework outperforms a built-in static recovery strategy in Erlang when a part obstract goes here.

Date 13 Mar 2017
Speakers
Session Types and Linear Logic and Lightweight Applications of Session Types in Java
PPVL Research Seminar, Department of Computer Science, UCL, March 2017

Session types is a well-established typing discipline for message passing concurrency, originally developed in the pi-calculus and later studied in functional and object-oriented settings. The first part of this talk is a tutorial on session types and its connections to linear logic. A recent interpretation of propositions as session types for intuitionistic linear logic has been given by Caires and Pfenning, viewing proofs as processes and proof reduction as inter-process communication. We discuss how several generalisations and extensions of this interpretation arguably form a basis for a logical foundation that captures several interesting features of message-passing concurrent computation. Specifically, we will detail how the basic interpretation can be extended to richer typed settings such as polymorphism and dependent type theories, and how to account for a notion of typed process equivalence that gives meaning to both proof conversions and type isomorphisms. We will then briefly introduce the key concepts and intuitions behind multiparty session types (MPST).

The second part of this talk will demonstrate Scribble, a toolchain based on MPST, and applications in Java by using MPST to generate protocol-specific APIs for implementing distributed endpoints. This practical approach builds on the linear understanding of session types as a hybrid form of session safety: the interaction structure of an endpoint is captured via static Java typing, complemented by lightweight run-time checks on linear usage of channels. Examples include Scribble specifications and Java implementations of interoperable clients/servers for standard protocols such as HTTP and SMTP, and Web service choreographies. Finally, we demonstrate a recent extension of MPST with explicit connection actions, that allow sessions with dynamic and optional participants.

Date 7 Mar 2017
Speakers
Let It Recover: Multiparty Protocol-Induced Recovery
Computer Science Seminar Series, University of Camerino, Italy

In this talk, first we summarise the recent activities on session types in Imperial College London http://mrg.doc.ic.ac.uk/.

Then we talk about a new recovery strategy in Erlang based on Multiparty session types, which was presented in 26th ACM International Conference on Compiler Construction (CC’17).

Fault-tolerant communication systems rely on recovery strategies which are often error-prone (e.g. a programmer manually specifies recovery strategies) or inefficient (e.g. the whole system is restarted from the beginning). In this talk, we will present an algorithm to efficiently compute a safe global state from which a system of interacting processes should be recovered. We statically analyse the communication flow of a program, given as a multiparty protocol, to extract the causal dependencies between processes and to localise failures. We formalise our recovery algorithm and prove its safety. A recovered communication system is free from deadlocks, orphan messages and reception errors. Our recovery algorithm incurs less communication cost (only affected processes are notified) and overall execution time (only required states are repeated). On top of our analysis, we design and implement a runtime framework in Erlang where failed processes and their dependencies are soundly restarted from a computed safe state. We evaluate our recovery framework on message-passing benchmarks and a use case for crawling web pages. The experimental results indicate our framework outperforms a built-in static recovery strategy in Erlang when a part of the protocol can be safely recovered.

Date 22 Feb 2017
Speakers
Multiparty Session Types and their Applications
Université Pierre et Marie Curie Paris 6, Dec 2016

We give a summary of our recent research developments on multiparty session types for verifying distributed, parallel and concurrent programs, and our collaborations with industry partners. We shall first outline the multiparty session types and then explain how we started collaborations with industry to develop a protocol description language called Scribble. We then talk about the recent developments in Scribble, the runtime session monitoring framework used in Ocean Observatories Initiative and network protocol verifications. We also demonstrate how our multiparty session synthesis theory is applied to Zero Deviation Life Cycle project with Cognizant; and static deadlock analysis for Google’s Go language.

Date 14 Dec 2016
Speakers
Compositionality and Session Types
Compositionality workshop, Simon's Institute for the Theory of Computing, University of California, Berkeley, Dec 2016

I shall talk about a difficulty to extend session types to be compositional in several contexts: multiparty session types, communicating automata and Linear Logic. I also talk about several solutions – some of them are motivated by practical applications of the session types.

Date 5 Dec 2016
Speakers
Building Graphical Choreographies From Communicating Machines: Principles and Applications
Seminaire Preuves, programmes et systèmes, University Paris-Diderot / IRIF, Nov 2016

Graphical choreographies, or global graphs, are general multiparty session specifications featuring expressive constructs such as forking, merging, and joining for representing application-level protocols. Global graphs can be directly translated into modelling notations such as BPMN and UML. In the first part of the talk, I will first present an algorithm whereby a global graph can be constructed from asynchronous interactions represented by communicating finite-state machines (CFSMs); and a sound characterisation of a subset of safe CFSMs from which global graphs can be constructed. In the second part, I will outline a few recent applications of this work to communicating timed automata and the Go programming language.

Date 29 Nov 2016
Speakers
Session Types and their Open Problems
COST Action BETTY final meeting, NOVA University of Lisbon, Portugal
Date 6 Oct 2016
Speakers
μServices and Scribble, a.k.a. Scribble @ ThoughtWorks
COST Action BETTY final meeting, NOVA University of Lisbon, Portugal

BETTY final project meeting keynote

Date 6 Oct 2016
Speakers
Multiparty Session Types and their Applications to Concurrent and Distributed Systems
Papers We Love Conference / Strange Loop 2016 preconference, St. Louis, MO, Sept 15-17, 2016

Nobuko Yoshida’s talk will present a summary of recent papers on multiparty session types for verifying distributed, parallel and concurrent programs, illustrating how theoretical work is grounded on collaborations with industry partners. This research led to the development of the protocol description language Scribble and other work such as static deadlock analysis in Go.

PWLConf 2016

Date 15 Sep 2016
Speakers
Building Graphical Choreographies From Communicating Machines: Principles and Applications
Computer Science Colloquium, University of Southern Denmark, Aug 2016

Graphical choreographies, or global graphs, are general multiparty session specifications featuring expressive constructs such as forking, merging, and joining for representing application-level protocols. Global graphs can be directly translated into modelling notations such as BPMN and UML. In the first part of the talk, I will first present an algorithm whereby a global graph can be constructed from asynchronous interactions represented by communicating finite-state machines (CFSMs); and a sound characterisation of a subset of safe CFSMs from which global graphs can be constructed. In the second part, I will outline a few recent applications of this work to communicating timed automata and the Go programming language.

Date 18 Aug 2016
Speakers
Static Deadlock Detection for Go
GolangUK 2016, 17-19 Aug 2016

Go’s concurrency features differ from mainstream programming languages in that they are based on the high-level and formal model of CSP (or process calculi) by Tony Hoare in 1978. Over the years, a large body of research work was developed for understanding concurrency based on process calculi, but rarely applied directly in programming languages. I will talk about a static analyser we developed for detecting deadlocks in Go, inspired by a research area which gives “types” to process calculi. In a nutshell, the tool infers “types” for communication between goroutines from Go source code, then construct a bird’s eye view of all communication (also called choreography or global graph) possible at runtime, through which deadlocks and communication problems are discovered.

This talk will focus on the work-in-progress aspects of the tool. No knowledge of CSP/process calculi are needed but some understanding of concurrency in Go and static analysis concepts are expected.

Date 17 Aug 2016 - 19 Aug 2016
Speakers
Synthesis of Multiparty Session Types
Nagoya University, Jul 2016

Multiparty session types are a type system that can ensure the safety and liveness of distributed peers via the global specification of their interactions. To construct a global specification from a set of distributed uncontrolled behaviours, this talk explores the problem of fully characterising multiparty session types in terms of communicating automata. We equip global and local session types with labelled transition systems (LTSs) that faithfully represent asynchronous communications through unbounded buffered channels. Using the equivalence between the two LTSs, we identify a class of communicating automata that exactly correspond to the projected local types. We exhibit an algorithm to synthesise a global type from a collection of communicating automata. The key property of our findings is the notion of multiparty compatibility which non-trivially extends the duality condition for binary session types.

At the end of the talk, I also show a couple of applications of the synthesis theory of multiparty session types.

Date 27 Jul 2016
Speakers
Synthesis of Multiparty Session Types
National Institute of Informatics (NII), July 2016

Multiparty session types are a type system that can ensure the safety and liveness of distributed peers via the global specification of their interactions. To construct a global specification from a set of distributed uncontrolled behaviours, this talk explores the problem of fully characterising multiparty session types in terms of communicating automata. We equip global and local session types with labelled transition systems (LTSs) that faithfully represent asynchronous communications through unbounded buffered channels. Using the equivalence between the two LTSs, we identify a class of communicating automata that exactly correspond to the projected local types. We exhibit an algorithm to synthesise a global type from a collection of communicating automata. The key property of our findings is the notion of multiparty compatibility which non-trivially extends the duality condition for binary session types.

At the end of the talk, I also show a couple of applications of the synthesis theory of multiparty session types.

Date 19 Jul 2016
Speakers
Multiparty Session Types and their Applications
NJ Programming Languages and Systems Seminar, University of Pennsylvania, May 2016

We give a summary of our recent research developments on multiparty session types for verifying distributed, parallel and concurrent programs, and our collaborations with industry partners. We shall first outline the multiparty session types and then explain how we started collaborations with industry to develop a protocol description language called Scribble. We then talk about the recent developments in Scribble, the runtime session monitoring framework used in Ocean Observatories Initiative and network protocol verifications. We also demonstrate how our multiparty session synthesis theory is applied to Zero Deviation Life Cycle project with Cognizant; and static deadlock analysis for Google’s Go language.

Date 16 May 2016
Speakers
Multiparty Session Types and their Applications
Departmental Seminar, School of Computer Science, The University of Manchester, May 2016

We give a summary of our recent research developments on multiparty session types for verifying distributed, parallel and concurrent programs, and our collaborations with industry partners. We shall first introduce the multiparty session types and then explain how we started collaborations with industry to develop a protocol description language called Scribble. We then talk about the recent developments in Scribble, the runtime session monitoring framework used in Ocean Observatories Initiative and network protocol verifications. We also demonstrate how our multiparty session synthesis theory is applied to Zero Deviation Life Cycle project in Cognizant; and static deadlock analysis for Google’s Go language.

Date 4 May 2016
Speakers
Multiparty Session Types and their Applications
Computer Science Seminar Series, Computer Science Division, School of Science and Technology, University of Camerino, Italy, April 2016

We give a summary of our recent research developments on multiparty session types for verifying distributed, parallel and concurrent programs, and our collaborations with industry partners. We shall first introduce the multiparty session types and then explain how we started collaborations with industry to develop a protocol description language called Scribble. We then talk about the recent developments in Scribble, the runtime session monitoring framework used in Ocean Observatories Initiative and network protocol verifications. We also demonstrate how our multiparty session synthesis theory is applied to Zero Deviation Life Cycle project in Cognizant; and static deadlock analysis for Google’s Go language.

Date 29 Apr 2016
Speakers
Phil & Session Types / Session Types & Linear Logic
WadlerFest - In celebration of Philip Wadler's 60th birthday, Informatics Forum, Edinburgh, Apr 2016
Date 11 Apr 2016 - 12 Apr 2016
Speakers
Earlier