8 - Concurrent communicating processes

Summary

In Chapter 5 we saw how one can describe parallel programs using structural operational semantics. Concurrenct behaviour is explained as the nondeterministic interleaving of the steps of the individual parallel components, so to describe this we employ a small-step semantics.

However, the language constructs considered in Chapter 5 allowed parallel components to communicate only by reading and modifying the values of shared variables. In this chapter we take a look at other paradigms for communication between concurrent processes.

The first language that we shall consider in Section 8.1 is very reminiscent of the process calculi CSP (Hoare, 1988) and CCS (Milner, 1989). The languages considered in later sections are all variants of this language.

Section 8.5 of the chapter is devoted to a short introduction to the area of behavioural equivalences for concurrent processes, and in particular to the notion of bisimulation.

CSP and CCS are early examples of process calculi, and the idea of bisimulation equivalence has become prominent here. A process calculus is a simple notation designed with the aim of being able to describe and reason about the behaviour of concurrent processes. The last section of the chapter describes a more recent and very important process calculus which has given rise to a large body of research. This process calculus, the π-calculus, is an expressive yet simple process calculus that allows one to describe phenomena such as references and the transfer of reference.