Department of Computer Science and Technology

Course pages 2018–19

Unit: Topics in Concurrency

This course is only taken by Part II 75% students.

Lecturers: Professor G. Winskel

No. of lectures and practical classes: 16

Prerequisite courses: Semantics of programming langauges (specifically, an idea of operational semantics and how to reason from it); some knowledge of Denotational Semantics will be helpful though not essential for the latter part on Games.

Capacity: no restrictions

Aims

The aim of this course is to introduce fundamental concepts and techniques in the theory of concurrent processes. It will provide languages, models, logics and methods to formalise and reason about concurrent systems.

Lectures

Simple parallelism and nondeterminism. Dijkstra’s guarded commands. Communication by shared variables: A language of parallel commands. [1 lecture]
Communicating processes. Milner’s Calculus of Communicating Processes (CCS). Pure CCS. Labelled-transition-system semantics. Bisimulation equivalence. Equational consequences and examples. [3 lectures]
Specification and model-checking. The modal mu-calculus. Its relation with Temporal Logic, CTL. Model checking the modal mu-calculus. Bisimulation checking. Examples. [3 lectures]
Introduction to Petri nets. Petri nets, basic definitions and concepts. Petri-net semantics of CCS. [1 lecture]
Cryptographic protocols. Cryptographic protocols informally. A language for cryptographic protocols. Its Petri-net semantics. Properties of cryptographic protocols: secrecy, authentication. Examples with proofs of correctness. [2 lectures]
Event structures. Their relation with Petri nets and representation via rigid families. The CCS operations on event stuctures. Maps of event structures. [2 lectures]
Games and strategies as event structures, an introduction to Concurrent Games. Composing strategies - interaction and hiding. A special case: nondeterministic dataflow. [2 lectures]
Strategies as concurrent processes. A higher-order language for strategies. May and must equivalence. Probabilistic and quantum strategies briefly. The future? [2 lectures]

Objectives

By the end of the course students should:

know the basic theory of concurrent processes: non-deterministic and parallel commands, the process language CCS, its transition-system semantics, bisimulation, the modal mu-calculus, Petri nets, event structures, a language and reasoning techniques for cryptographic protocols, and the basics of concurrent games;
be able to formalise and to some extent analyse concurrent processes: establish bisimulation or its absence in simple cases, express and establish simple properties of transition systems in the modal mu-calculus, argue with respect to a process language semantics for secrecy or authentication properties of a small cryptographic protocol, apply the basics of concurrent games.

Unit: Topics in Concurrency

Aims

Lectures

Objectives

Recommended reading