Communicating and Mobile Systems: The Pi-Calculus

by Robin Milner

Communication is a fundamental and integral part of computing, whether between different computers on a network, or between components within a single computer. In this book Robin Milner introduces a new way of modelling communication that reflects its position. He treats computers and their programs as themselves built from communicating parts, rather than adding communication as an extra level of activity. Everything is introduced by means of examples, such as mobile phones, job schedualers, vending machines, data structures, and the objects of object-oriented programming. But the aim of the book is to develop a theory, the pi-calculus, in which these things can be treated rigorously. The pi-calculus differs from other models of communicating behaviour mainly in its treatment of mobility. The movement of a piece of data inside a computer program is treated exactly the same as the transfer of a message--or indeed an entire computer program--across the internet. One can also describe networks which reconfigure themselves. The calculus is very simple but powerful; its most prominent ingredient is the notion of a name. Its theory has two important ingredients: the concept of behavioural (or observational) equivalence, and the use of a new theory of types to classify patterns of interactive behaviour. The internet, and its communication protocols, fall within the scope of the theory just as much as computer programs, data structures, algorithms and programming languages. This book is the first textbook on the subject; it has been long-awaited by professionals and will be welcome by them, and their students.

Genres: Computer Science, Nonfiction

176 pages, Paperback

First published May 20, 1999

Reviews

[Sheffielder · Rating 5 out of 5]

The pi-calculus is a beautiful language! Just as the lambda-calculus was invented to model computations, so the pi-calculus was invented to model processes. Milner's earlier work on CCS set the scene, but it only dealt with concurrency; since mobility wasn't included in the primitive operations, it was hard to model things like mobile phone networks, the internet, or network security.

The change from CCS to pi-calculus is as far-reaching as it is straightforward: you simply allow channel names to be passed as messages from process to process. You can literally model any computable function in terms of pi-calculus process interactions.

This book introduces the pi-calculus, and shows you how to model simple systems using it. There are examples of buffers and so forth to set the scene, and readers should learn enough to model real-world systems. However, pi-calculus (like CCS before it) is more than just a language for describing things; it also lets you reason about them. Milner explains some of the basic equivalences on processes, and shows how you can use processes to model data. He also discusses the possibility of adding a type theory to the language.

Pi-calculus is by no means simple, so this book definitely requires some mathematical maturity of its readers. But my experience using it as a course text book is that students find the calculus relatively straightforward provided it's explained well, and you give plenty of examples.

All in all, a great subject, and a great book to learn it from, especially if you couple it with the two online tutorials still available from LFCS (where Milner and his colleagues used to work when they invented the calculus). Sangiorgi and Walker's book is better for advanced researchers, but if you want an introductory book that explains the language in non-trivial terms, this is the one for you.

[Clement Janssens · Rating 4 out of 5]

A great, rather approachable introduction to the pi calculus and tangent concepts important in the world of process calculi. Not the most comprehensive book though. Probably because it was published so long ago.