进程代数的历史，介绍进程代数的发展过程

A Brief History of Process Algebra

J.C.M. Baeten

Department of Computer Science, Technische Universiteit Eindhoven,

P.O. Box 513, 5600 MB Eindhoven, The Netherlands

josb@win.tue.nl

Abstract. This note addresses the history of pro ces s algebra as an area

of research in concurrency theory, the theory of parallel and distributed

systems in computer science. Origins are traced back to the early sev-

enties of the twentieth century, and developments since that time are

Computer science is a very young science, that has its origins in the middle of the

twentieth century. For this reason, describing its history, or the history of an area

of research in computer science, is an activity that receives scant attention. The

organizers of a workshop on process algebra in Bertinoro in July 2003 (see [2])

aimed at describing the current state of affairs and future directions of research

in process algebra, an active area of research in computer science. In planning

the workshop, the question came up how the present situation came about. I

was asked to investigate the history of process algebra.

This note addresses the history of process algebra as an area of research in

concurrency theory, the theory of parallel and distributed systems in computer

needed in order for the theories to appear. I consider the development of CCS,

CSP and ACP. In Section 4, I sketch the main developments since then.

Let me stress that I give my personal views on what are the central issues

and the important breakthroughs. Others may well have very different views. I

welcome discussion, in order to get a better and more complete account. I briefly

consider the present situation, and state some challenges for the future.

2 J.C.M. Baeten

Acknowledgement

The author gratefully acknow ledges the discussions at the Process Algebra: Open

Problems and Future Directions Workshop in Bertinoro in July 2003 (see [2]).

In particular, I would like to mention input from Jan Friso Groote [44] and Luca

events or actions that a system can perform, the order in which they can be exe-

cuted and maybe other aspects of this execution such as timing or probabilities.

Always, we describe certain aspects of behaviour, disregarding other aspects, so

we are considering an abstraction or idealization of the ‘real’ behaviour. Rather,

we can say that we have an observation of behaviour, and an action is the chosen

unit of observation. Usually, the actions are thought to be discrete: occurrence

is at some moment in time, and different actions are separated in time. This is

why a process is sometimes also called a discrete event system.

The word ‘algebra’ denotes that we take an algebraic/axiomatic approach in

talking about behaviour. That is, we use the methods and techniques of universal

So, a group is any mathematical structure with operators satisfying the group

axioms. Stated differently: a group is any model of the equational theory of

groups. Likewise, we can say that a process algebra is any mathematical structure

satisfying the axioms given for the basic operators. A process is an element of a

process algebra. By using the axioms, we can perform calculations with pro ce ss es.

The simplest model of behaviour is to see behaviour as an input/output

function. A value or input is given at the beginning of the process, and at some

moment there is a(nother) value as outcome or output. This model was used

century. It was instrumental in the development of (finite state) automata theory.

In automata theory, a process is modeled as an automaton. An automaton has a

number of states and a number of transitions, going from one state to a(nother)

state. A transition denotes the execution of an (elementary) action, the basic

unit of behaviour. Besides, there is an initial state (sometimes, more than one)

executions from the initial state to a final state. An algebra that allows equational

reasoning about automata is the algebra of regular expressions (see e.g. [58]).

Later on, this model was found to be lacking in several situations. Basically,

what is missing is the notion of interaction: during the execution from initial

state to final state, a system may interact with another system. This is needed

in order to describe parallel or distributed systems, or so-called reactive sys-

tems. When dealing with interacting sys tems , we say we are doing concurrency

theory, so concurrency theory is the theory of interacting, parallel and/or dis-

tributed systems . When talking about process algebra, we usually consider it as

an approach to concurrency theory, so a process algebra will usually (but not

algebra, i.e. equational reasoning. By means of this equational reasoning, we can

do verification, i.e. we c an establish that a system satisfies a certain property.

What are these basic laws of process algebra? We can list some, that are

usually called structural or static laws. We start out from a given set of atomic

actions, and use the basic op erators to compose these into more complicated pro-

cesses. As basic operators, we use + denoting alternative composition, ; denoting

sequential composition and k denoting parallel composition. Usually, there are

also neutral elements for some or all of these operators, but we do not consider

these here. Some basic laws are the following (+ binding weakest, ; binding

strongest).

These laws are called static laws because they do not mention action execu-

sition. In some cases, other connections are considered. On the other hand, we

list no law connecting parallel composition to the other operators. It turns out

such a connection is at the heart of process algebra, and it is the to ol that makes

calculation possible. In most process algebras, this law allows to express parallel

4 J.C.M. Baeten

composition in terms of the other operators, and is called an expansion theorem.

So, we can say that any mathematical structure with three binary operations

satisfying these 7 laws is a process algebra. Most often, these structures are

formulated in terms of automata, in this case mostly called transition systems.

This means a transition system has a number of states and transitions between

them, an initial state and a number of final states. The notion of equivalence

studied is usually not language equivalence. Prominent among the equivalences

studied is the notion of bisimulation. Often, the study of transition systems,

ways to define them and e quivalences on them are also considered part of process

algebra, even in the case no equational theory is present.

In this note, I will be more precise: process algebra is the study of pertinent

3 History

The history of process algebra will be traced back to the early seventies of the

twentieth century. At that point, the only part of c oncurrency theory that existed

is the theory of Petri nets, conceived by Petri starting from his thesis in 1962 [84].

In 1970, we can distinguish three main styles of formal reasoning about computer

programs, focusing on giving semantics (meaning) to programming languages.

1. Operational semantics. A computer program is modeled as an execution of

an abstract machine. A state of such a machine is a valuation of variables, a

grams correct. Central notions are program assertions, proof triples consist-

ing of precondition, program statement and postcondition, and invariants.

Pioneers are Floyd [38] and Hoare [53].

Then, the question was raised how to give semantics to programs contain-

made (for instance, see [50]).

There are two paradigm shifts that need to made, before a theory of parallel

programs in terms of a proce ss algebra can be developed. First of all, the idea of

a behaviour as an input/output function needed to be abandoned. A program