zbMATH — the first resource for mathematics

Communicating sequential processes. Repr. (English) Zbl 0841.68042
Prentice Hall International Series in Computer Science. New York, NY: Prentice Hall. viii, 256 p. (1995).
This book gives an overview of Communicating Sequential Processes, a formal theory of concurrent computation. First, the basic concept of a process as a mathematical abstraction of the interactions between a system and its environment is introduced by giving graphical illustrations, algebraic laws and an implementation in terms of a functional programming language. The author then shows how the behaviour of a process can be recorded as a trace of the sequence of actions in which it engages. Rules are given to help in the implementation of processes which can be proved to meet their specification. The second chapter describes how processes can be assembled together into systems, in which the components interact with each other and with their external environment. The introduction of concurrency does not by itself introduce any element of nondeterminism. The main example of this chapter treats the problem of the five dining philosophers. Furthermore, processes can be conveniently adapted to new purposes by changing names of the events in which they engage. The chapter concludes with an explanation of the mathematical theory of deterministic processes, including a simple account of the domain theory of recursion. The third chapter considers nondeterminism, a technique for achieving abstraction from the concrete behaviour of a system. A complete formal definition of the concept of a nondeterministic process is given. Chapter 4 introduces communication, a special case of synchronous interaction between two processes. The design of some simple systolic (or iterative) array algorithms illustrates the use of concurrent systems to achieve greater speed of computation. Chapter 5 shows how the conventional operators of sequential programming can be integrated within the framework of communicating sequential processes. Chapter 6 shows how to structure and implement a system in which a limited number of physical resources (such as disks and line printers) can be shared among a greater number of processes, whose resource requirements vary with time. Each resource is represented as a single process. On each occasion that a resource is required by a user process, a new virtual resource is created. A virtual resource is a process which behaves as if it were subordinate to the user process; but it also communicates with the real resource whenever required. Such communications are interleaved with those of other concurrently active virtual processes. The chapter is illustrated by the modular development of a series of complete but very simple operating systems. Chapter 7, finally, describes a number of alternative approaches to concurrency and communication, and explains the technical, historical, and personal motives which led to the theory of Communicating Sequential Processes.

68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science
68Q65 Abstract data types; algebraic specification