Example problems for concurrent computation

Question

There's a plethora of paradigms and methods for concurrent programming in use today. Software transactional memory, actors, shared state concurrency, tuple spaces and many, many more.

What I find lacking, however, is a library of interesting test problems for concurrency. One well known example is the "Dining Philosophers Problem", which is neither a complex enough nor motivating nor realistic one. Then there are many parallel algorithms (matrix multiplication, rendering, general nested data parallelism) that just require distribution of work, but no real concurrency with communication between threads of execution.

So, can anyone point me to some interesting sets of problems that require real concurrency in an interactive, perhaps even distributed environment, that are simple enough to use as examples for concurrency paradigms? Ideally, I want to find a set of problems to serve as a "lackmus-test" for concurrency paradigms (or to highlight their differences, as every paradigm has its strengths and weaknesses).

Any help is much appreciated :)

Answer 1

I've previously considered this exact issue, having previously proposed some concurrent programing paradigms myself :p

The conclusion I reached then is that such a test set doesn't seem to really exist in a language-independent manner. While it might be helpful for it to exist, there seem to be some fairly good reasons it doesn't (to the best of my knowledge).

Most of the focus within concurrent programming tends to be on data parallelism, such that the same operation is applied in parallel to different pieces of the same data set. The kinds of task-level parallelism (i.e. different tasks being performed in parallel, possibly sharing data) that I think you're talking about is actually not done very much. I think this is because it's kinda hard. But I think it's also kinda hard because most problems don't lend themselves particularly well to this kind of concurrency. Describing a distributed system in terms of concurrency primitives may be helpful, but these systems tend to be decoupled such that there is a protocol (written or implied) moderating their communication. People tend not to think of these kinds of systems as obviously "concurrent" programming situations, even though they are when viewed within the right frame (i.e. considering the "client" and "server" as agents operating in parallel with synchronisation at some points).

The only places I think you could find some sources of inspiration would be within individual implementations. Erlang, Occam (and Occam-pi), Alice, CML, Concurrent Haskell etc all are likely to have small test corpuses, but both the problems and their implementations are going to be biased towards being implementable within a specific language (because they obviously are implementable within that language!). Perhaps you could also look to the communities working on multi-party session types, and various process calculi such as pi-calculus, CCS and CSP to see what kinds of systems they are using as example models. The idea of a standard language-agnostic set of problems for describing concurrent communicating systems is appealing, but somewhat elusive at this point, I think.