1 - INTRODUCTION

Summary

Many computing systems consist of a possibly large number of components that not only work independently or concurrently, but also interact or communicate with each other from time to time. Examples of such systems are operating systems, distributed systems and communication protocols, as well as systolic algorithms, computer architectures and integrated circuits.

Conceptually, it is convenient to treat these systems and their components uniformly as concurrent processes. A process is here an object that is designed for a possibly continuous interaction with its user, which can be another process. An interaction can be an input or output of a value, but we just think of it abstractly as a communication. In between two subsequent communications the process usually engages in some internal actions. These proceed autonomously at a certain speed and are not visible to the user. However, as a result of such internal actions the process behaviour may appear nondeterministic to the user. Concurrency arises because there can be more than one user and inside the process more than one active subprocess. The behaviour of a process is unsatisfactory for its user(s) if it does not communicate as desired. The reason can be that the process stops too early or that it engages in an infinite loop of internal actions. The first problem causes a deadlock with the user(s); the second one is known as divergence. Thus most processes are designed to communicate arbitrarily long without any danger of deadlock or divergence.