ACM Computing Surveys 28A(4), December 1996, http://www.acm.org/pubs/citations/journals/surveys/1996-28-4es/a40-best/. Copyright © 1996 by the Association for Computing Machinery, Inc. See the permissions statement below.

Some Major Dichotomies
Relating to Future Research in Concurrency

Eike Best

Universität Oldenburg, Fachbereich Informatik (Theoretische Informatik, Parallele Systeme),
Postfach 25 03, 26111 Oldenburg, Germany
eike.best@informatik.uni-oldenburg.de, http://theoretica.informatik.uni-oldenburg.de/personal/Best.Eike.html

1 Introduction

The past decades have seen various advances in the theory of concurrency. Nevertheless, the issues involved are by their nature hard and many questions remain unsolved. In particular, the dictum: `get as simple as possible but not simpler' has not yet been achieved for languages and formal models used in concurrency. In my opinion, in addition to the ones already enjoying wide attention at present (such as achieving unifications of models), three challenges are of major concern and importance.

2. Correctness versus efficiency

The languages and (sometimes overly complicated) formal models used in semantics and verification of parallel systems are still almost disjoint from the languages and (sometimes overly idealised) formal models used in parallel complexity theory. The challenge is to create a basis for the study of the two basic concerns of any design - correctness and efficiency - within the same (or at least within a significantly compatible) formal framework.

3. Automatability versus heuristics

Automated verification can only be part of the answer when it comes to ensuring the correctness of a design. Automated parallelisation can only be part of the answer when it comes to distributing an algorithm efficiently on a multiprocessor system. Both must be complemented by heuristic guidelines - linking a specification with its realisation - which can be taught in classes to improve the skills of designers and programmers. The challenge is to complement known heuristics for sequential systems by a set of new heuristics guaranteeing correct and efficient use of the `parallel operator'.

4. General purpose languages versus hardware topologies

Concurrency adds another dimension to the idea of general-purpose programming languages. There is as yet no language that allows one to express parallel algorithms of wide variety and, at the same time, can be implemented efficiently on a wide spectrum of hardware topologies. Creating a parallel system involves exploiting parallelism inherent in the problem while being constrained by parallelism available on the target machine. The challenge is to cope with this dichotomy by designing a good general-purpose general-topology concurrent language. If (as seems likely) this cannot be achieved easily, the challenge is to embark on designing a spectrum of languages serving, as a whole, a similar purpose. This may involve standardising a set of guidelines for creating different general-purpose languages for different machines.

References

[Best 1996]: Best, E., 1996. Some Major Dichotomies Relating to Future Research in Concurrency, Computing Surveys, 28A, 4 (December), http://www.acm.org/pubs/citations/journals/surveys/1996-28-4es/a40-best/

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or permissions@acm.org.

Last modified: Sat Nov 16 12:00:00 MET 1996