ACM Computing Surveys 28A(4), December 1996, http://www.acm.org/surveys/1996/WolperAlgorithmic. Copyright © 1996 by the Association for Computing Machinery, Inc. See the permissions statement below.

Pierre Wolper

The algorithmic support of concurrency theories needs neither be immediate nor direct. A semantics can eventually lead to a reliable compiler. Temporal logic was studied for several years before algorithmic synthesis and verification methods appeared. However, research that ignores the issue often becomes a blind alley. Consider for instance the issue of compositionality in proof systems for concurrency. I am not going to argue that compositionality is undesirable, but that achieving it without algorithmic support (in a broad sense) is easy and mostly useless. Indeed, if you can code programs and the concurrent composition rule in a logic, the logic becomes compositional. But, that does not help much. What matters is to be able to effectively reason about the concurrent composition of programs. Rephrasing this problem as the problem of reasoning in a logic does not help, it can even make things harder.

There are many questions still to consider in concurrency theory [CS 1996]. One can look for more comprehensive models, for a unifying framework, for better languages, or for more discriminating semantics. All this is valuable, but will be even more so if we keep asking ``where is the algorithmic support?''

References

[CS 1996]

Rance Cleaveland and Scott A. Smolka Eds, Strategic Directions in Computing Research Concurrency Working Group Report Computing Surveys, 28, 4 (December 1996), http://www.cs.sunysb.edu/~sas/sdcr/report/final/final.html

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.