Distributed Termination

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

Distributed Termination

Full text

Pdf (795 KB)

Source

ACM Transactions on Programming Languages and Systems (TOPLAS) archive
Volume 2 , Issue 1 (January 1980) table of contents

Pages: 42 - 55

Year of Publication: 1980

ISSN:0164-0925

Author

Nissim Francez

Department of Computer Science, Technion-Israel Institute of Technology, Haifa, Israel

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 67, Citation Count: 43

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/357084.357087 What is a DOI?

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

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Per Brinch Hansen, The Architecture of Concurrent Programs, Prentice Hall PTR, Upper Saddle River, NJ, 1977
	2	Per Brinch Hansen, Distributed processes: a concurrent programming concept, Communications of the ACM, v.21 n.11, p.934-941, Nov. 1978 [doi>10.1145/359642.359651]
	3	DE BAKKER, j.W. Semantics and termination of nondeterministic recursive programs. Proc. 4th Conf. on Automata, Languages, and Programming, 1976.
	4	DIJKSTRA, E.W. A class of simple communication patterns. EDW-643, 1978.
	5	DIJKSTRA, E.W. A correctness proof for communicating processes--A small exercise. EDW-607, 1977.
	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.
	7	C. A. R. Hoare, Communicating sequential processes, Communications of the ACM, v.21 n.8, p.666-677, Aug. 1978 [doi>10.1145/359576.359585]
	8	George Milne , Robin Milner, Concurrent Processes and Their Syntax, Journal of the ACM (JACM), v.26 n.2, p.302-321, April 1979 [doi>10.1145/322123.322134]
	9	Si~Tzorr, M. On language design for program construction. Centre de Recherche en Informatique, Jan. 1978.
	10	WIRTH, N. Modula--A programming language for modular programming. Sofiw. Pract. Experi. 7, 2 (March 1977).

CITED BY 43

	Shimon Cohen , Daniel Lehmann, Dynamic systems and their distributed termination, Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, p.29-33, August 18-20, 1982, Ottawa, Canada
	Gregory R. Andrews, Paradigms for process interaction in distributed programs, ACM Computing Surveys (CSUR), v.23 n.1, p.49-90, March 1991
	L. Bougé , N. Francez, A compositional approach to superimposition, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.240-249, January 10-13, 1988, San Diego, California, United States
	D. Kumar, Development of a Class of Distributed Termination Detection Algorithms, IEEE Transactions on Knowledge and Data Engineering, v.4 n.2, p.145-155, April 1992
	Edgar Knapp, Deadlock detection in distributed databases, ACM Computing Surveys (CSUR), v.19 n.4, p.303-328, Dec. 1987
	R. J. R. Back , R. Kurki-Suonio, Decentralization of process nets with centralized control, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.131-142, August 17-19, 1983, Montreal, Quebec, Canada
	Shmuel Katz, A superimposition control construct for distributed systems, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.2, p.337-356, April 1993
	Laurent Pautet , Samuel Tardieu, What future for the distributed systems annex?, ACM SIGAda Ada Letters, v.XIX n.3, p.77-82, Sept. 1999
	Prasad Vishnubhotla, Fine-grain parallelism in the ALPS programming language, Proceedings of the 1990 conference on Supercomputing, p.506-514, October 1990, New York, New York, United States
	Yehuda Afek , Michael Saks, Detecting global termination conditions in the face of uncertainty, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.109-124, August 10-12, 1987, Vancouver, British Columbia, Canada
	Abha Moitra, Synthesis of communicating processes, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.123-130, August 17-19, 1983, Montreal, Quebec, Canada
	Jayadev Misra, Detecting termination of distributed computations using markers, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.290-294, August 17-19, 1983, Montreal, Quebec, Canada
	Krzysztof R. Apt , Nissim Francez , Willem P. de Roever, A Proof System for Communicating Sequential Processes, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.3, p.359-385, July 1980
	Jayadev Misra , K. M. Chandy, Termination Detection of Diffusing Computations in Communicating Sequential Processes, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.1, p.37-43, Jan. 1982
	Ouri Wolfson , Aya Ozeri, A new paradigm for parallel and distributed rule-processing, ACM SIGMOD Record, v.19 n.2, p.133-142, Jun. 1990
	Ouri Wolfson , Hasanat M. Dewan , Salvatore J. Stolfo , Yechiam Yemini, Incremental evaluation of rules and its relationship to parallelism, ACM SIGMOD Record, v.20 n.2, p.78-87, June 1991
	David R. Jefferson, Virtual time, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.3, p.404-425, July 1985
	C. Mohan, Technical Correspondence: On Francez's ``Distributed Termination'', ACM Transactions on Programming Languages and Systems (TOPLAS), v.3 n.1, p.112, Jan. 1981
	Mani Chandy , Jayadev Misra, An example of stepwise refinement of distributed programs: quiescence detection, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.3, p.326-343, July 1986
	S. -T. Huang, A distributed deadlock detection algorithm for CSP-like communication, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.1, p.102-122, Jan. 1990
	C. Cheng , I. Cimet , S. Kumar, A protocol to maintain a minimum spanning tree in a dynamic topology, ACM SIGCOMM Computer Communication Review, v.18 n.4, p.330-337, August 1988
	G. Castelli , F. De Cindio , G. De Michelis , C. Simone, An overview of the GCP programming language, Proceedings of the 1985 ACM SIGSMALL symposium on Small systems, p.245-253, May 1985, Danvers, Massachusetts, United States
	B. Szymanski , Y. Shi , N. Prywes, Terminating iterative solution of simultaneous equations in distributed message passing systems, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.287-292, August 1985, Minaki, Ontario, Canada
	Nissim Francez, Extended naming conventions for communicating processes, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.40-45, January 25-27, 1982, Albuquerque, Mexico
	A. Singh , J. Schaeffer , M. Green, A Template-Based Approach to the Generation of Distributed Applications Using a Network of Workstations, IEEE Transactions on Parallel and Distributed Systems, v.2 n.1, p.52-67, January 1991
	D. Kumar, Systems with Low Distributed Simulation Overhead, IEEE Transactions on Parallel and Distributed Systems, v.3 n.2, p.155-165, March 1992
	Krzysztof R. Apt, Correctness proofs of distributed termination algorithms, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.3, p.388-405, July 1986
	Jeff Matocha, Distributed termination detection in a mobile wireless network, Proceedings of the 36th annual Southeast regional conference, p.207-213, April 1998
	Jean-Michael Helary , Claude Jard , Noël Plouzeau , Michel Raynal, Detection of stable properties in distributed applications, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.125-136, August 10-12, 1987, Vancouver, British Columbia, Canada
	Carol Critchlow , Kim Taylor, The inhibition spectrum and the achievement of causal consistency, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.31-42, August 22-24, 1990, Quebec City, Quebec, Canada
	Carol Critchlow , Kim Taylor, The inhibition spectrum and the achievement of causal consistency, Distributed Computing, v.10 n.1, p.11-27, July 1996
	Jeff Kramer , Jeff Magee, The Evolving Philosophers Problem: Dynamic Change Management, IEEE Transactions on Software Engineering, v.16 n.11, p.1293-1306, November 1990
	Chengzhong Xu , Francis C. M. Lau, Efficient Termination Detection for Loosely Synchronous Applications in Multicomputers, IEEE Transactions on Parallel and Distributed Systems, v.7 n.5, p.537-544, May 1996
	Jacques M. Bahi , Sylvain Contassot-Vivier , Raphael Couturier , Flavien Vernier, A Decentralized Convergence Detection Algorithm for Asynchronous Parallel Iterative Algorithms, IEEE Transactions on Parallel and Distributed Systems, v.16 n.1, p.4-13, January 2005
	Prakash Panangaden , Kim Taylor, Concurrent common knowledge: defining agreement for asynchronous systems, Distributed Computing, v.6 n.2, p.73-93, September 1992
	Jean-Michel Hélary , Michel Raynal, Towards the construction of distributed detection programs, with an application to distributed termination, Distributed Computing, v.7 n.3, p.137-147, March 1994
	Robert D. Falgout , Jim E. Jones , Ulrike Meier Yang, Pursuing scalability for hypre's conceptual interfaces, ACM Transactions on Mathematical Software (TOMS), v.31 n.3, p.326-350, September 2005
	Krzysztof R. Apt , Nissim Francez, Modeling the distributed termination convention of CSP, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.3, p.370-379, July 1984
	Gerard Tel , Friedemann Mattern, The derivation of distributed termination detection algorithms from garbage collection schemes, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.1, p.1-35, Jan. 1993
	Gruia-Catalin Roman , Jamie Payton, A Termination Detection Protocol for Use in Mobile Ad Hoc Networks, Automated Software Engineering, v.12 n.1, p.81-99, January 2005
	D. Talla, Notes on termination of OCCAM processes, ACM SIGPLAN Notices, v.25 n.9, p.17-24, Sep. 1990
	Neeraj Mittal , Felix C. Freiling , S. Venkatesan , Lucia Draque Penso, On termination detection in crash-prone distributed systems with failure detectors, Journal of Parallel and Distributed Computing, v.68 n.6, p.855-875, June, 2008
	Neeraj Mittal , Kuppahalli L. Phaneesh , Felix C. Freiling, Safe termination detection in an asynchronous distributed system when processes may crash and recover, Theoretical Computer Science, v.410 n.6-7, p.614-628, February, 2009