The problem with process "algebras", 11 May 2009

(from my departmental pages)

Process algebras like CCS and CSP do not begin with a precise semantics. I have written elsewhere in detail about CCS but let's look at an example from CSP. In Chapter 2 of his classic book Communicating sequential processes (Prentice Hall), C.A.R. Hoare describes the dining philosopher problem i) as a circular arrangement of philosophers and forks, and ii) as (Philosophers)||(Forks). These hint at geometrically quite different systems.

The truth is that the first picture is not represented in CCS, and that the real idea behind CCS is that there is a broadcast of signals between the philosophers and the forks.

To make the point more crudely, instead of the philosophers communicating with adjacent forks, they have to scramble in the middle of the table to find their forks. It is clear that these two different systems are quite different.

The situation becomes worse when the process algebras are used to investigate timing, and probability. The natural way of assigning duration or probabities to processes depends very much on the precise system we have in mind, as is clear from the two different pictures I described above.

The matter is serious. A theory of processes has much to add, for example, to probability theory. We must abandon these "algebras" based on broadcast!

The idea of producing a calculus before having a precise model goes back to the lambda calculus of Alonzo Church, which was invented about 1928, but which did not have a model till Dana Scott produced one on 14th November 1969.