To my knowledge, there are three major process algebras that have inspired a vas

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 ?-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?

Explanation / Answer

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!

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.