article

Open access

The multiway rendezvous

Editor: Susan L. Graham Author:

Arthur CharlesworthAuthors Info & Claims

ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 9, Issue 3

Pages 350 - 366

https://doi.org/10.1145/24039.24050

Published: 01 July 1987 Publication History

PDF eReader

Abstract

The multiway rendezvous is a natural generalization of the rendezvous in which more than two processes may participate. The utility of the multiway rendezvous is illustrated by solutions to a variety of problems. To make their simplicity apparent, these solutions are written using a construct tailor-made to support the multiway rendezvous. The degree of support for multiway rendezvous applications by several well-known languages that support the two-way rendezvous is examined. Since such support for the multiway rendezvous is found to be inadequate, well-integrated extensions to these languages are considered that would help provide such support.

References

[1]

ADAMS, L. M. Iterative algorithms for large sparse linear systems on parallel computers. Contract. Rep. 166027, NASA Langley Research Center, Hampton, Va., Nov. 1982.

Google Scholar

[2]

AHO, A. V., HOPCROFT, J. E., AND ULLMAN, J. D. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass., 1974.

Crossref

Google Scholar

[3]

ANDREWS, G.R. Synchronizing Resources. ACM Trans. Program. Lang. Syst. 3, 4 (Oct. 1981), 405-430.

Crossref

Google Scholar

[4]

BERNSTEIN, A.J. Output guards and nondeterminism in "Communicating Sequential Processes." ACM Trans. Program. Lang. Syst. 2, 2 (Apr. 1980), 234-238.

Crossref

Google Scholar

[5]

BRINCH HANSEN, P. Distributed Processes: A concurrent programming concept. Commun. ACM 21, 11 (Nov. 1978), 934-941.

Crossref

Google Scholar

[6]

BUCKLEY, G. N., AND SILBERSCHATZ, A. An effective implementation for the generalized inputoutput construct of CSP. ACM Trans. Program. Lang. Syst. 5, 2 (Apr. 1983), 223-235.

Crossref

Google Scholar

[7]

CHARLESWORTH, A. Communication and synchronization using compacts. M.S. thesis, Dept. of Applied Mathematics and Computer Science, Univ. of Virginia, Charlottesville, Va., Aug. 1983.

Google Scholar

[8]

DEO, N., AND YO0, Y. B. Parallel algorithms for the minimum spanning tree problem. In Proceedings of the 1981 International Con{erence on Parallel Processing, (Bellaire, Mich., Aug. 25-28, 1981). Ohio State Univ., Columbus, 1981, pp. 188-189.

Google Scholar

[9]

DEO, N., PANG, C. Y., AND LORD, R.E. Two parallel algorithms for shortest path problems. In Proceedings o{ the 1980 International Conference on Parallel Processing, (Pellston, Mich., Aug. 26-29, 1980). Wright State Univ., Dayton, Oh., 1980, pp. 244-253.

Google Scholar

[10]

GRIES, D. The Science o{ Programming. Springer-Verlag, New York, 1981.

Crossref

Google Scholar

[11]

HOARE, C. A. R. Communicating sequential processes. Commun. ACM 21, 8 (Aug. 1978), 666-677.

Crossref

Google Scholar

[12]

HOCKNEY, R. W., AND JESSHOPE, C.R. Parallel Computers: Architecture, Programming and Algorithms. Hilger, London, U.K., 1981.

Crossref

Google Scholar

[13]

QUINN, M.J. The design and analysis of algorithms and data structures for the efficient solution of graph theoretic problems on MIMD computers. Ph.D. dissertation, Dept. of Computer Science, Washington State Univ., Pullman, Wash., 1983.

Crossref

Google Scholar

[14]

United States Department of Defense. Reference manual for the Ada programming language. ANSI/MIL-STD-1815A-1983, American National Standards Institute, New York, 1983.

Google Scholar

[15]

WILLIAMS, G. Computational Linear Algebra with Models. Allyn and Bacon, Boston, Mass., 1975.

Google Scholar

[16]

YEMINI, S. On the suitability of Ada multitasking for expressing parallel algorithms. In Proceedings o{ the AdaTEC Con~erence on Ada (Arlington, Va., Oct. 6-8, 1982). ACM, New York, 1982, pp. 91-97.

Google Scholar

Cited By

View all

Horel JLedent PMarsso LMuller LLaugier CMateescu RPaigwar ARenzaglia ASerwe W(2023)Verifying Collision Risk Estimation using Autonomous Driving Scenarios Derived from a Formal ModelJournal of Intelligent and Robotic Systems10.1007/s10846-023-01808-3107:4Online publication date: 21-Apr-2023
https://dl.acm.org/doi/10.1007/s10846-023-01808-3
Horel JLaugier CMarsso LMateescu RMuller LPaigwar ARenzaglia ASerwe WBolchini CO'Connor IVerbauwhede IWille R(2022)Using formal conformance testing to generate scenarios for autonomous vehiclesProceedings of the 2022 Conference & Exhibition on Design, Automation & Test in Europe10.5555/3539845.3539969(532-537)Online publication date: 14-Mar-2022
https://dl.acm.org/doi/10.5555/3539845.3539969
Horel JLaugier CMarsso LMateescu RMuller LPaigwar ARenzaglia ASerwe W(2022)Using Formal Conformance Testing to Generate Scenarios for Autonomous Vehicles2022 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE54114.2022.9774581(532-537)Online publication date: 14-Mar-2022
https://doi.org/10.23919/DATE54114.2022.9774581
Show More Cited By

Recommendations

An SR approach to multiway rendezvous

This paper presents a new approach to programming multiway rendezvous problems in the SR language. The approach uses SR's concurrent invocation statement and rendezvous mechanism to coordinate the interacting processes. This approach is compared with ...
On multiway cut parameterized above lower bounds

We introduce a concept of parameterizing a problem above the optimum solution of its natural linear programming relaxation and prove that the node multiway cut problem is fixed-parameter tractable (FPT) in this setting. As a consequence we prove that ...
Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
SODA '12: Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms

Given a directed graph G, a set of k terminals and an integer p, the Directed Vertex Multiway Cut problem asks if there is a set S of at most p (nonterminal) vertices whose removal disconnects each terminal from all other terminals. Directed Edge ...

Reviews

Reviewer: Peter Milligan

This paper presents what the author suggests is a natural generalization of the well-known concept of a two-way rendezvous. The generalization, called a multiway rendezvous (MR), extends the function of the two-way rendezvous to an n-process state; that is, execution of a denoted statement sequence is permitted when and only when a specified number of processes reach a corresponding point in their execution sequences. The paper examines the use of the new rendezvous technique and investigates language support for such a structure. The author also indicates that the purpose of the paper is to suggest a strategy for concurrent programming. The main section of the paper comprises three units. The first unit introduces a structure referred to as a compact that is used to “encapsulate” the MR. The second unit demonstrates the use of the MR, that is, the compact, in a number of applications. The final unit examines how existing languages that support the two-way rendezvous also support the MR. The aim of the paper is to present original research and it does so in a satisfactory manner. The paper is well structured and use of the MR is demonstrated with an acceptable range of examples. In the conclusions the author makes it clear that he does not claim that the MR is appropriate for use in the majority of concurrent programs. This view should not be allowed to mar an excellent paper that presents a well-argued case for the use of the MR and the need for its inclusion in appropriate high-level languages. The lack of a formal specification of the semantics of the compact may be viewed with concern, but this omission does not detract significantly from the paper. The paper will interest anyone working in the general concurrent programming area and can be recommended to those with specific interests in parallel programming methodology and the design of languages to support parallel programming. The latest reference in the paper is from 1983, which is somewhat dated. This problem arises from the long delays that have become part of the publication cycle, so the criticism may be somewhat unjustified. Finally, there appears to be a minor error in the program presented on page 353, where an entry called INIT appears in a display:.US entry:.US block for compact COM but is referred to as COM.INT in both process X:.US WORKER and process PROJECTION. The correct entry in X:.US WORKER and PROJECTION should be COM.INIT.

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Programming Languages and Systems

ACM Transactions on Programming Languages and Systems Volume 9, Issue 3

July 1987

166 pages

ISSN:0164-0925

EISSN:1558-4593

DOI:10.1145/24039

Editor:
Susan L. Graham

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1987

Published in TOPLAS Volume 9, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

57
Total Citations
View Citations
512
Total Downloads

Downloads (Last 12 months)55
Downloads (Last 6 weeks)5

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Horel JLedent PMarsso LMuller LLaugier CMateescu RPaigwar ARenzaglia ASerwe W(2023)Verifying Collision Risk Estimation using Autonomous Driving Scenarios Derived from a Formal ModelJournal of Intelligent and Robotic Systems10.1007/s10846-023-01808-3107:4Online publication date: 21-Apr-2023
https://dl.acm.org/doi/10.1007/s10846-023-01808-3
Horel JLaugier CMarsso LMateescu RMuller LPaigwar ARenzaglia ASerwe WBolchini CO'Connor IVerbauwhede IWille R(2022)Using formal conformance testing to generate scenarios for autonomous vehiclesProceedings of the 2022 Conference & Exhibition on Design, Automation & Test in Europe10.5555/3539845.3539969(532-537)Online publication date: 14-Mar-2022
https://dl.acm.org/doi/10.5555/3539845.3539969
Horel JLaugier CMarsso LMateescu RMuller LPaigwar ARenzaglia ASerwe W(2022)Using Formal Conformance Testing to Generate Scenarios for Autonomous Vehicles2022 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE54114.2022.9774581(532-537)Online publication date: 14-Mar-2022
https://doi.org/10.23919/DATE54114.2022.9774581
Lambertz CMajster-Cederbaum M(2013)Efficient deadlock analysis of component-based software architecturesScience of Computer Programming10.1016/j.scico.2013.02.00678:12(2488-2510)Online publication date: Dec-2013
https://doi.org/10.1016/j.scico.2013.02.006
Raynal MRaynal M(2013)Rendezvous (Synchronous) CommunicationDistributed Algorithms for Message-Passing Systems10.1007/978-3-642-38123-2_13(335-364)Online publication date: 2013
https://doi.org/10.1007/978-3-642-38123-2_13
Martens MMajster-Cederbaum M(2012)Deadlock-freedom in component systems with architectural constraintsFormal Methods in System Design10.1007/s10703-012-0160-641:2(129-177)Online publication date: 1-Oct-2012
https://dl.acm.org/doi/10.1007/s10703-012-0160-6
Cheung EChen XHsieh HDavare ASangiovanni-Vincentelli AWatanabe Y(2009)Runtime deadlock analysis for system level designDesign Automation for Embedded Systems10.1007/s10617-009-9046-213:4(287-310)Online publication date: 1-Dec-2009
https://dl.acm.org/doi/10.1007/s10617-009-9046-2
Chen XDavare AHsieh HSangiovanni-Vincentelli AWatanabe YJoyner WMartin GKahng A(2005)Simulation based deadlock analysis for system level designsProceedings of the 42nd annual Design Automation Conference10.1145/1065579.1065647(260-265)Online publication date: 13-Jun-2005
https://dl.acm.org/doi/10.1145/1065579.1065647
Xi Chen Davare AHsieh HSangiovanni-Vincentelli AWatanabe Y(2005)Simulation based deadlock analysis for system level designsProceedings. 42nd Design Automation Conference, 2005.10.1109/DAC.2005.193812(260-265)Online publication date: 2005
https://doi.org/10.1109/DAC.2005.193812
Frølund SAgha G(2005)Abstracting interactions based on message setsObject-Based Models and Languages for Concurrent Systems10.1007/3-540-59450-7_7(107-124)Online publication date: 1-Jun-2005
https://doi.org/10.1007/3-540-59450-7_7
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

An SR approach to multiway rendezvous

On multiway cut parameterized above lower bounds

Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset

Reviews

Access critical reviews of Computing literature here