Re: Cost of Choise operators in CSP?

[Adam Sampson <A.T.Sampson@xxxxxxxxxx>]

JoÃl-Alexis Bialkiewicz <joel-alexis@xxxxxxxxxxxxxx> writes:

> I wonder how Occam does it.

The short answer is that it doesn't -- occam only allows choice over
input communications and timers, not over output communications over
barrier synchronisations, so it doesn't provide full CSP choice. This
simplifies the problem considerably.

It's implemented in different ways on different occam implementations.
The Transterpreter pretty much follows the original Transputer approach.
CCSP is a bit more complex, because it schedules work across multiple
threads, and is described in this paper:
  http://www.cs.kent.ac.uk/pubs/2009/2928/

(The usual justification for why occam doesn't support arbitrary choice
is that because priorities in occam are specified in the PRI ALT
construct, rather than being attached to events themselves, allowing
choice over both ends of a channel would allow inconsistent priorities
to be specified at the two ends -- e.g. process 1 can prefer A over B,
and process 2 can prefer B over A. This has so far largely turned out
not to be a problem in practice for environments that do support
arbitrary choice!)

A simple way to resolve CSP-style multiway choice if you're not too
worried about scalability is just to record everybody's offers somewhere
central, and then scan the list to find completed
synchronisations. Peter came up with a way of doing this easily in
software:
  http://www.cs.kent.ac.uk/pubs/2006/2398/
and Alastair/Oliver/Bernhard did the same for hardware:
  http://wotug.org/paperdb/send_file.php?num=229

Thanks,

-- 
Adam Sampson                                         <http://offog.org/>