AbstractA multiparty interaction is a set of I/O actions executed jointly by a number of processes, each of which must be ready to execute its own action for any of the actions in the set to occur. An attempt to participate in an interaction delays a process until all other participants are available. Although a relatively new concept, the multiparty interaction has found its way into a number of distributed programming languages and algebraic models of concurrency.
In this paper, we present a taxonomy of languages for multiparty interaction that covers all proposals of which we are aware. Based on this taxonomy, we then present a comprehensive analysis of the computational complexity of the multiparty interaction scheduling problem, the problem of scheduling multiparty interactions in a given execution environment.
The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.
Preliminary versionA preliminary version of these results was presented in: Yuh-Jzer Joung and Scott A. Smolka. A comprehensive study of the complexity of multiparty interaction. In Conference Record of the Nineteenth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 142-153, Albequerque, New Mexico, January 1992.
Categories and Subject Descriptors: D.1.3 [Programming Techniques]: Concurrent Programming; D.3.2 [Programming Languages]: Language Classifications; D.3.3 [Programming Languages]: Language Constructs and Features -- concurrent programming structures, input/output; D.4.1 [Operating Systems]: Process Management -- synchronization; D.4.4 [Operating Systems]: Communications Management -- input/output; D.4.7 [Operating Systems]: Organization and Design -- distributed systems; F.2.3 [Analysis of Algorithms and Problem Complexity]: Tradeoffs among Complexity Measures
General Terms: Languages, Design, Theory
Additional Key Words and Phrases: Distributed languages, multiparty interaction, multiparty interaction scheduling, taxonomy
Selected references
- Gregory R. Andrews, Ronald A. Olsson, Michael H. Coffin, Irving Elshoff, Kelvin Nilsen, Titus Purdin, and Gregg M. Townsend. An overview of the SR language and implementation. ACM Transactions on Programming Languages and Systems, 10(1):51-86, January 1988.
- Krzysztof R. Apt, Nissim Francez, and Willem P. de Roever. A proof system for communicating sequential processes. ACM Transactions on Programming Languages and Systems, 2(3):359-385, July 1980.
- R. J. R. Back and R. Kurki-Suonio. Distributed cooperation with action systems. ACM Transactions on Programming Languages and Systems, 10(4):513-554, October 1988.
- Arthur Charlesworth. The multiway rendezvous. ACM Transactions on Programming Languages and Systems, 9(3):350-366, July 1987.
- David Gelernter. Generative communication in linda. ACM Transactions on Programming Languages and Systems, 7(1):80-112, January 1985.
- C. A. R. Hoare. Corrigendum: {``Communicating Sequential Processes''}. Communications of the ACM, 21(11):958-958, November 1978. See \cite{Hoare:1978:CSP}.
- Yuh-Jzer Joung and Scott A. Smolka. Coordinating first-order multiparty interactions. ACM Transactions on Programming Languages and Systems, 16(3):954-985, May 1994.
- Silvio Micali and Vijay V. Vazirani. An O(\sqrt{|v|} \cdot |E|) algorithm for finding maximum matching in general graphs. In 21st Annual Symposium on Foundations of Computer Science, pages 17-27, Syracuse, New York, 13-15 October 1980. IEEE.
- George J. Milne. Circal and the representation of communication, concurrency, and time. ACM Transactions on Programming Languages and Systems, 7(2):270-298, April 1985.
- Robin Milner. Calculi for synchrony and asynchrony. Theoretical Computer Science, 25(3):267-310, July 1983. Fundamental study.
- Robert de Simone. Higher-level synchronising devices in Meije-SCCS. Theoretical Computer Science, 37(3):245-267, December 1985. Fundamental studies.