article

Open access

Distributed Termination

Editor: Susan L. Graham Author:

Nissim FrancezAuthors Info & Claims

ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 2, Issue 1

Pages 42 - 55

https://doi.org/10.1145/357084.357087

Published: 01 January 1980 Publication History

PDF eReader

Abstract

Discussed is a distributed system based on communication among disjoint processes, where each process is capable of achieving a post-condition of its local space in such a way that the conjunction of local post-conditions implies a global post-condition of the whole system. The system is then augmented with extra control communication in order to achieve distributed termination, without adding new channels of communication. The algorithm is applied to a problem of constructing a sorted partition.

References

[1]

BRINCH HANSEN, P. The Architecture of Concurrent Programming. Prentice-Hall, Englewood Cliffs, N.J., 1977.

Crossref

Google Scholar

[2]

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

Crossref

Google Scholar

[3]

DE BAKKER, j.W. Semantics and termination of nondeterministic recursive programs. Proc. 4th Conf. on Automata, Languages, and Programming, 1976.

Google Scholar

[4]

DIJKSTRA, E.W. A class of simple communication patterns. EDW-643, 1978.

Google Scholar

[5]

DIJKSTRA, E.W. A correctness proof for communicating processes--A small exercise. EDW-607, 1977.

Google Scholar

[6]

FRANCEZ, N., HOARE, C.A.R., LEHMANN, J.D., DE ROEVER, W.P. Semantics ofnondeterminism, concurrency, and communication. To appear in J. Comput. Syst. Sci.

Google Scholar

[7]

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

Crossref

Google Scholar

[8]

MILNE, G., AND MILNER, R. Concurrent processes and their syntax. J. ACM 26, (April 1979), 302-321.

Crossref

Google Scholar

[9]

Si~Tzorr, M. On language design for program construction. Centre de Recherche en Informatique, Jan. 1978.

Google Scholar

[10]

WIRTH, N. Modula--A programming language for modular programming. Sofiw. Pract. Experi. 7, 2 (March 1977).

Google Scholar

Cited By

View all

Sinha BSingh ASaini P(2023)Termination detection in cloudInternational Journal of System Assurance Engineering and Management10.1007/s13198-023-02080-214:6(2337-2344)Online publication date: 18-Aug-2023
https://doi.org/10.1007/s13198-023-02080-2
Blin LJohnen CLe Bouder GPetit F(2022)Silent Anonymous Snap-Stabilizing Termination Detection2022 41st International Symposium on Reliable Distributed Systems (SRDS)10.1109/SRDS55811.2022.00023(156-165)Online publication date: Sep-2022
https://doi.org/10.1109/SRDS55811.2022.00023
Bougé L(2022)On the existence of symmetric algorithms to find leaders in networks of communicating sequential processesActa Informatica10.1007/BF0026358425:2(179-201)Online publication date: 10-Mar-2022
https://dl.acm.org/doi/10.1007/BF00263584
Show More Cited By

Index Terms

Distributed Termination
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features

Recommendations

Synchronized Distributed Termination

An efficient decentralized algorithm for synchronized termination of a distributed computation is presented. It is assumed that distributed processes are connected via unidirectional channels into a strongly connected network, in which no central ...
Achieving Distributed Termination without Freezing

An efficient algorithm for achieving distributed termination without introducing new communicaton channels and without delaying the basic computations ("freezing") is presented. The algorithm is related to the methodology of designing distributed ...
Abstraction refinement for termination
SAS'05: Proceedings of the 12th international conference on Static Analysis

Abstraction can often lead to spurious counterexamples. Counterexample-guided abstraction refinement is a method of strengthening abstractions based on the analysis of these spurious counterexamples. For invariance properties, a counterexample is a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1980

Published in TOPLAS Volume 2, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

197
Total Citations
View Citations
854
Total Downloads

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

Reflects downloads up to 30 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Sinha BSingh ASaini P(2023)Termination detection in cloudInternational Journal of System Assurance Engineering and Management10.1007/s13198-023-02080-214:6(2337-2344)Online publication date: 18-Aug-2023
https://doi.org/10.1007/s13198-023-02080-2
Blin LJohnen CLe Bouder GPetit F(2022)Silent Anonymous Snap-Stabilizing Termination Detection2022 41st International Symposium on Reliable Distributed Systems (SRDS)10.1109/SRDS55811.2022.00023(156-165)Online publication date: Sep-2022
https://doi.org/10.1109/SRDS55811.2022.00023
Bougé L(2022)On the existence of symmetric algorithms to find leaders in networks of communicating sequential processesActa Informatica10.1007/BF0026358425:2(179-201)Online publication date: 10-Mar-2022
https://dl.acm.org/doi/10.1007/BF00263584
Benner PNayak PCojean TAnzt H(2021)Evaluating asynchronous Schwarz solvers on GPUsInternational Journal of High Performance Computing Applications10.1177/109434202094681435:3(226-236)Online publication date: 30-Dec-2021
https://dl.acm.org/doi/10.1177/1094342020946814
Karlos GFokkink WFuchs P(2021)Fault-Tolerant Termination Detection with Safra’s AlgorithmNetworked Systems10.1007/978-3-030-91014-3_5(71-87)Online publication date: 19-May-2021
https://dl.acm.org/doi/10.1007/978-3-030-91014-3_5
Schuchart JBouteiller ABosilca G(2019)Using MPI-3 RMA for Active Messages2019 IEEE/ACM Workshop on Exascale MPI (ExaMPI)10.1109/ExaMPI49596.2019.00011(47-56)Online publication date: Nov-2019
https://doi.org/10.1109/ExaMPI49596.2019.00011
Durand AKutten S(2019)Reducing the Number of Messages in Self-stabilizing ProtocolsStabilization, Safety, and Security of Distributed Systems10.1007/978-3-030-34992-9_12(133-148)Online publication date: 14-Nov-2019
https://doi.org/10.1007/978-3-030-34992-9_12
Blom K(2018)Personal Note: Working with Farhad Arbab 1990–2005It's All About Coordination10.1007/978-3-319-90089-6_5(68-69)Online publication date: 7-Apr-2018
https://doi.org/10.1007/978-3-319-90089-6_5
Durand AKutten S(2018)Message-Efficient Self-stabilizing Transformer Using Snap-Stabilizing Quiescence DetectionStructural Information and Communication Complexity10.1007/978-3-030-01325-7_3(20-24)Online publication date: 31-Oct-2018
https://doi.org/10.1007/978-3-030-01325-7_3
Mishra RSaini P(2016)A weight throwing and diffusing computation based approach for termination detection in MANETs2016 Fourth International Conference on Parallel, Distributed and Grid Computing (PDGC)10.1109/PDGC.2016.7913114(50-55)Online publication date: 2016
https://doi.org/10.1109/PDGC.2016.7913114
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

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

Abstract

References

Cited By

Index Terms

Recommendations

Synchronized Distributed Termination

Achieving Distributed Termination without Freezing

Abstraction refinement for termination

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations