Similarities and differences in major process algebras

Question

To my knowledge, there are three major process algebras that have inspired a vast range of research into formal models of concurrency. These are:

• CCS and $\pi$-calculus both by Robin Milner
• CSP by Tony Hoare and
• ACP by Jan Bergstra and Jan Willem Klop

All three seem to have to this day a quite active following and vast amounts of research has been done on them.

What are the key similarities and differences of these approaches? Why has research in process algebra diverged instead of converged, in the sense that there is no one universal model to unify the field?

Answer 1

I only know CSP and CCS/pi-calculus (not ACP).

CSP was motivated by imperative programming processes communicating via messages. Hoare then tried to abstract away a simple calculus out of it. CCS, on the other hand, was an effort to create a foundational calculus like lambda calculus. Given their original starting points, and given their final form, I would say that they have converged rather than diverged.

What I find common between CSP and CCS is that both of them are based on the notion of "process" (and, by that, I mean an abstract notion of events arranged in time). The main difference between them is that CSP has two forms of choice (internal/external or nondeterministic/deterministic). In CCS the two ideas are fused into one. I think that is an irreconcilable difference.

The distinction between internal and external choice allows CSP to have a semantics in terms of linear traces. The CCS semantics, on the other hand, has to be based on trees.

I think Hoare's current plan for "Unifying theories" is to put both of them into a single framework. We have to wait and see what he comes up with!

Answer 2

Another partial answer.

The approach to semantics taken by the various communities differed, at least originally.

• ACP semantics are axiomatic/algebraic.
• CSP semantics are denotational, generally in terms of traces.
• CCS/$\pi$-calculus semantics are operational, generally in terms of labelled transition systems.

Of course, since the original semantics, more models have been developed. But it is certainly interesting that the original researchers started out with different semantic approaches.

Answer 3

Answering (at least) the part of your question regarding why research has diverged instead of converged.

Being no expert on process algebras, I was once wondering the exact same thing: why are there so many theories? I was pointed to a survey by Parrow: Expressiveness of Process Algebras, 2008. I think it is very nicely written and even a novice could understand it.

Parrow investigates the expressiveness of algebras and answers the question. In short, different theories are different kind of tools for solving a huge task.