Paper Details

Communicating Process Architectures (CPA)
 Title: Message-Passing Concurrency Shootout
 Conference: Communicating Process Architectures 2015
 Authors: Kevin Chalmers
School of Computing, Edinburgh Napier University
 Abstract:
Background
In the last few years there has been a number of new programming languages which incorporate message passing concurrency. Examples such as Google's Go and Mozilla's Rust have shown an increased industry and academic interest in the ideas of message passing concurrency as a first order concern. These languages have joined existing ones such as occam-pi, Erlang, and Ada with strong communication based concurrency. It is therefore argued that the concurrent systems programmer has a number of options for exploiting message based concurrency.

The Communicating Process Architectures (CPA) community and others have for a number of years developed libraries to support message passing concurrency within existing programming languages and runtimes. This support is normally built upon the thread support libraries of the host language. JCSP and PyCSP are commonly discussed, but support for CPA ideas has also been implemented in Haskell, C++, Lua, and other languages.

The languages and libraries supporting message passing concurrency are normally inspired by one of more process algebras. Hoare's Communicating Sequential Processes (CSP) and Milner's pi-calculus are the two main inspirations for message passing work. It is questionable however how well these process algebras are supported in the languages and libraries they inspire.

Action
The aim of this workshop is the development of a message passing language and library based shootout in a similar manner to that seen at The Computer Language Benchmarks Game, although looking at more than just performance. The metrics produced will be augmented by a discussion on support for the principals of CSP, CCS, and the pi-calculus. The work undertaken, and further development, will lead to the production of a journal publication focusing on CPA languages and libraries, providing a state-of-the-art review. The paper produced will summarise the results and provide further dissemination of CPA ideas to a wider audience. The test applications built will be made available on a repository and the results published via arxiv for accessibility outside the paper. The workshop is looking for people interested in producing the test applications in the various languages and libraries.

There are two questions that the work undertaken will attempt to answer:
  - How well supported are the primitives and ideas of CSP, CCS, and the pi-calculus in the range of languages and libraries supporting message passing concurrency?
  - What are the metrics of the languages and libraries supporting message passing concurrency?

For the first question a set of criteria is required to define what we mean by process algebra support. This requires definition of what a process algebra provides. The key ideas are message passing passing and event selection, with the ability to spawn off processes (execute in parallel). As a starting point, the current list of properties of interest are:
  - Message passing support (this is the minimum criteria)
  - Type of message passing support - synchronous and/or asynchronous
  - First Order Channels (not all languages provide a channel construct)
  - Higher Order Channels (channels that can send channels)
  - First order processes (also a minimum criteria)
  - Higher order processes (channels can send processes)
  - Parallel execution statement
  - Process ownership (e.g. a parallel cannot complete until all its child processes have)
  - Selection on incoming messages
  - Other selection types? (e.g. skip, timeout)
  - Selection on outgoing messages
  - Multiway synchronisation

For the second question, a look at the metrics that help define the performance and usefulness of the languages is required. CPA typically uses the CommsTime and StressedAlt benchmarks. These two benchmarks allow analysis of the two key properties in a communication based language or library - communication time and selection time. The memory usage of a process is also required, or an equivalent measure. The aim would be to understand the number of processes the language or library can support. Knowing whether the language or library exploited parallel hardware (e.g. multicore) is also important. Typical software metrics such as Lines of Code (LoC), time, speedup, efficient, memory usage, and CPU usage for the following applications is a possible starting point:
  - CommsTime - channel communication time
  - StressedAlt - selection time and maximum process support
  - Dining Philosophers - LoC
  - Vector Addition - simple data parallel problem
  - Matrix Multiplication - complex data parallel problem
  - Mandelbrot - data parallel with large data output
  - Monte Carlo Pi - data parallel with low data output and reduction
  - N-body simulation - shared data

The current set of languages I have come across that reportedly support message passing concurrency are:

   Ada, Ateji PX, Clojure, D, Elixir, Erlang, Go, Guppy, Hume, Kilim, Hume, Limbo, Nim, occam-pi, Oz, ProcessJ, Perl, Rust, Unicon

As for the set of libraries:

   JCSP, CTJ, C++CSP, PyCSP, C Haskell P, C Scala P, CCSP, LuaCSP

A discussion on whether to include all actor based languages and libraries is also required, as if these are included the number of libraries and languages will increase. 
Files:


BibTeX Entry


Full paper


Presentation