Communicating sequential processes

de:Communicating Sequential Processes

In computer science, Communicating Sequential Processes (CSP) is a language for describing patterns of interaction. First described in a paper by C. A. R. Hoare in 1978, the basic ideas in that paper were refined into the book “Communicating Sequential Processes” which was published in 1985. In May 2005, that book was still the third-most cited (http://citeseer.ist.psu.edu/articles.html) computer science reference of all time according to Citeseer (albeit a very unreliable source due to the nature of it sampling).

As its name suggests, CSP allows us to describe systems as a number of components (processes) which operate independently and communicate with each other solely over well-defined channels. CSP introduces a process algebra which is used to describe a process' communications with its environment.

a -> P is the process which is willing to communicate a with its environment and after a, behaves like the process P.

STOP represents the process which can communicate nothing. It is also called deadlock.

P [] Q is the process which is willing to communicate the first events of P or of Q and then behaves accordingly. This represents deterministic choice - the environment chooses which events are done.

P |~| Q can behave like either P or Q. It can refuse to accept the first events of P or of Q and is only obliged to communicate if the environment offers both. This represents nondeterministic choice - the process can choose which events should be done. Nondeterminism can be introduced by a seemingly deterministic process as in the following:

(a -> a -> STOP) [] (a -> b -> STOP) = a -> ((a -> STOP) |~| (b -> STOP))

To give the archetypal CSP example; an abstract representation of a chocolate machine might be able to carry out two different events, “coin” and “choc” which represent the insertion of payment and the delivery of a chocolate respectively. A machine which demanded payment before offering a chocolate could be written as:

coin -> choc -> STOP

A person who might choose to use a coin or card could be modelled as:

(coin -> STOP) [] (card -> STOP)

These two processes can be put in parallel, the resulting processes depending on the events they must synchronise on. If this was both “coin” and “card”, the resulting process would be:

coin -> choc -> STOP

whereas if synchronization was only required on “coin”, the resulting process would be:

(coin -> choc -> STOP) [] (card ->STOP)

Events can be abstracted in CSP by various mechanisms such as hiding events and renaming events. If we hide the “coin” and “card” events from the second of the combined processes, we get the nondeterministic process:

(choc -> STOP) |~| STOP

This is a process which either offers a “choc” event and then stops, or just stops. In other words, if we treat the abstraction as an external view of the system (eg. someone who does not see the decision reached by the person), a nondeterminism has been introduced.

See also

• Occam is a practical implementation of CSP as a programming language.
• JCSP is a binding of CSP & Occam concepts in a Java thread support API.
• Linda
• MPI
• PVM
• Actor model
• Calculus of Communicating Systems
• Calculus of Broadcasting Systems

References

• C. A. R. Hoare: Communicating Sequential Processes, Prentice-Hall, ISBN 0-13-153271-8. This book has been updated by Jim Davies at the Oxford University Computer Laboratory and the new edition is available for download as a pdf file at the Using CSP (http://www.usingcsp.com/) website.
• A. W. Roscoe: The Theory and Practice of Concurrency, Prentice-Hall, ISBN 0-13-674409-5. Some links relating to this book are available here (http://web.comlab.ox.ac.uk/oucl/publications/books/concurrency/). The full text is available for download as a PS (http://web.comlab.ox.ac.uk/oucl/work/bill.roscoe/publications/68b.ps) or pdf (http://web.comlab.ox.ac.uk/oucl/work/bill.roscoe/publications/68b.pdf) file from Bill Roscoe's list (http://web.comlab.ox.ac.uk/oucl/work/bill.roscoe/pubs.html) of academic publications.
• Gregory R. Andrews: Foundations of Multithreaded, Parallel, and Distributed Programming, Addison-Wesley, ISBN 0-201-35752-6

External links

• CSP Archive (http://comlab.ox.ac.uk/archive/csp.html)
• Virtual library of Formal methods (http://www.afm.sbu.ac.uk/csp/)
• WoTUG (http://www.wotug.org/), the World Occam and Transputer User Group web site contains some information about CSP and useful links.
• Formal Systems (http://www.fsel.com/) develop CSP tools, some of which are freely downloadable.
• Concurrency Research Group (http://www.cs.kent.ac.uk/research/groups/crg/research_interests.html)
• Citations from CiteSeer (http://citeseer.org/cs?q=Communicating+and+Sequential+and+Processes)