Skip to main content
SpringerLink
Log in

Algorithms for distributed termination detection

  • Published:
Distributed Computing Aims and scope Submit manuscript

Abstract

The termination problem for distributed computations is analyzed in the general context of asynchronous communication. In the underlying computational model it is assumed that messages take an arbitrary but finite time and do not necessarily obey the FIFO rule. Time diagrams are used as a graphic means of representing the overall communication scheme, giving a clear insight into the difficulties involved (e.g., lack of global state or time, inconsistent time cuts) and suggesting possible solutions.

Several efficient algorithms for the solution of the termination problem are presented. They are all based on the idea of message counting but have a number of different characteristics. The methods are discussed and compared with other known solutions.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Apt KR, Richier J-L (1985) Real time clocks versus virtual clocks. In: Broy M (ed) Control flow and data flow: Concepts of distributed programming. Springer, Berlin Heidelberg New York, pp 475–501

    Google Scholar 

  • Apt KR (1986) Correctness proofs of distributed termination algorithms. ACM Trans Program Lang Syst 8 (3):388–405

    Google Scholar 

  • Arora RK, Sharma NK (1983) A methodology to solve distributed termination problem. Inf Syst 8 (1):37–39

    Google Scholar 

  • Beilken C, Mattern F, Reinfrank M (1985) Verteilte Terminierung — ein wesentlicher Aspekt der Kontrolle in verteilten Systemen. Report SFB124-41/85, Department of Computer Science, University of Kaiserlautern, FRG

    Google Scholar 

  • Bougé L (1985a) Symmetry and genericity for CSP in distributed systems. Report 85-32, LITP, Universite Paris 7, France

    Google Scholar 

  • Bougé L (1985b) Repeated synchronous snapshots and their implementation in CSP. In: Brauer W (ed) 12th Coll Automata, Lang and Programming. Springer, Berlin Heidelberg New York, LNCS 194, pp 63–70

    Google Scholar 

  • Chandy KM, Mirsa J, Haas LM (1983) Distributed deadlock detection. ACM Trans Comput Syst 1 (2):144–156

    Google Scholar 

  • Chandy KM, Lamport L (1985) Distributed snapshots: Determining global states of distributed systems. ACM Trans Comput Syst 3 (1):63–75

    Google Scholar 

  • Chandy KM, Misra J (1985) A paradigm for detecting quiescent properties in distributed computations. In: Apt KR (ed) Logics and models of concurrent systems. Springer, Berlin Heidelberg New York, pp 325–341

    Google Scholar 

  • Chandy KM, Misra J (1986) An example of stepwise refinement of distributed programs: quiescence detection. ACM Trans Program Lang Syst 8 (3):326–343

    Google Scholar 

  • Chang EJH (1982) Echo algorithms: Depth parallel operations on general graphs. IEEE Trans Software Eng SE 8 (4):391–401

    Google Scholar 

  • Clinger WD (1981) Foundations of actor semantics. Report AI-TR-633, Artificial Intelligence Laboratory, Massachusetts Institute of Technology, USA

    Google Scholar 

  • Cohen S, Lehman D (1982) Dynamic systems and their distributed termination. Proc ACM SIGACT-SIGOPS Symp Principles Distributed Comput, Ottawa, pp 29–33

  • Dijkstra EW, Scholten CS (1980) Termination detection for diffusing computations. Inf Process Lett 11 (1):1–4

    Google Scholar 

  • Dijkstra EW, Feijen WHJ, van Gasteren AJM (1983) Derivation of a termination detection algorithm for distributed computations. Inf Process Lett 16 (5):217–219

    Google Scholar 

  • Francez N (1980) Distributed termination. ACM Trans Program Lang Syst 2 (1):42–55

    Google Scholar 

  • Francez N, Rodeh M, Sintzoff M (1981) Distributed termination with interval assertions. In: Diaz J, Ramos I (eds) Proc Int Colloq Formalization of Programming Concepts. Springer, Berlin Heidelberg New York, LNCS 107, pp 280–289

    Google Scholar 

  • Francez N, Rodeh M (1982) Achieving distributed termination without freezing. IEEE Trans Software Eng SE-8 (3):287–292

    Google Scholar 

  • Kumar D (1985) A class of termination detection algorithms for distributed computations. In: Mahheshwari N (ed) 5th Conf on Foundations of Software Technology and Theoretical Computer Science, New Delhi. Springer, Berlin Heidelberg New York, LNCS 206, pp 73–100

    Google Scholar 

  • Lai T-H (1985) Termination detection for dynamic distributed systems with non-first-in-first-out communication. Report 85-16, Computer and Information Science Research Center. Ohio State University, Columbus, USA

    Google Scholar 

  • Lai T-H (1986) A termination detector for static and dynamic distributed systems with asynchronous non-first-in-first-out communication. In: Kott L (ed) 13th Coll Automata, Lang and Programming. Springer, Berlin Heidelberg New York, LNCS 226, pp 196–205

    Google Scholar 

  • Lamport L (1978) Time, clock and the ordering of events in a distributed system. Commun ACM 21 (7):558–565

    Google Scholar 

  • Lavallee I, Roucairol G (1986) A fully distributed (minimal) spanning tree algorithm. Inf Process Lett 23:55–62

    Google Scholar 

  • Lozinskii EL (1984) Yet another distributed termination. Report 84-2, Department of Computer Science, The Hebrew University of Jerusalem, Israel

    Google Scholar 

  • Lozinskii EL (1985) A remark on distributed termination. Proc 5th Internat Conf on Distributed Computing Systems, Denver, pp 416–419

  • Mattern F, Beilken C (1985) The distributed programming language CSSA—a short introduction. Report 123/85, Department of Computer Science, University of Kaiserslautern, FRG

    Google Scholar 

  • Mattern F (1986) Asynchronous distributed termination—parallel and symmetric solutions with echo algorithms. Report SFB124-21/87, Department of Computer Science, University of Kaiserslautern, FRG

    Google Scholar 

  • Misra J, Chandy KM (1982) Termination detection of diffusing computations in communicating sequential processes. ACM Trans Program Lang Syst 4 (1):37–43

    Google Scholar 

  • Misra J (1983) Detecting termination of distributed computations using markers. Proc 2nd Ann ACM Symp Principles Distributed Comput, Montreal, Quebec, pp 290–294

  • Nehmer J et al. (1987) Key concepts of the INCAS multicomputer project. IEEE Trans Software Eng SE-13 (8):913–923

    Google Scholar 

  • Rana SP (1983) A distributed solution of the distributed termination problem. Inf Process Lett 17 (1):43–46

    Google Scholar 

  • Richier J-L (1985) Distributed termination in CSP: Symmetric solutions with minimal storage. In: Mehlhorn K (ed) Proc STACS 85. Springer, Berlin Heidelberg New York, LNCS 182, pp. 267–278

    Google Scholar 

  • Rozoy B (1986) Model and complexity of termination for distributed computations. In: Gruska J, Rovan B, Wiedermann J (eds) Proc Math Found Comp Sc 86. Springer, Berlin Heidelberg New York, LNCS 233, pp 564–572

    Google Scholar 

  • Shavit N, Francez N (1986) A new approach to detection of locally indicative stability. Report RC 11925 (# 53703), IBM Thomas J Watson Research Center, Yorktown Heights, USA

    Google Scholar 

  • Tan RB, van Leeuwen J (1986) General symmetric distributed termination detection. Report RUU-CS-86-2, Department of Computer Science, University of Utrecht, The Netherlands

    Google Scholar 

  • Tel G (1986) Distributed infimum approximation. Report RUU-CS-86-12, Department of Computer Science, University of Utrecht, The Netherlands

    Google Scholar 

  • Tel G, Tan RB, van Leeuwen J (1986) The derivation of graph marking algorithms from distributed termination detection protocols. Report RUU CS-86-11, Department of Computer Science, University of Utrecht, The Netherlands

    Google Scholar 

  • Topor RW (1984) Termination detection for distributed computations. Inf Process Lett 18 (1):33–36

    Google Scholar 

  • Szymanski B, Shi Y, Prywes NS (1985) Synchronized distributed termination. IEEE Trans Software Eng SE-11 (10):1136–1140

    Google Scholar 

Note added in proof

  • Afek Y, Saks M (1987) Detecting global termination conditions in the face of uncertainty. Techn Rep, Bell Laboratories, Murray Hill, USA

    Google Scholar 

  • Augusteijn L (1986) Establishing global assertions in a distributed environment. ESPRIT project 415, Doc. No 183, Philips Research Laboratories, Eindhoven, The Netherlands

    Google Scholar 

  • Arora RK, Rana SP, Gupta MN (1986) Distributed termination detection algorithm for distributed computations. Inf Process Lett 22:311–314 [The algorithm is wrong. See Tan RB, Tel G, Van Leeuwen J (1986) Comments on “Distributed termination detection algorithm for distributed computations”. Inf Process Lett 23:163

    Google Scholar 

  • Chandrasekaran S, Kannan CS, Venkatesan S (1987) Efficient distributed termination detection. Proc IFIP Conf Distributed Processing. North-Holland, Amsterdam New York Oxford

    Google Scholar 

  • Dijkstra EW (1987) Shmuel Safra's version of termination detection. Report EWD998-0, Department of Computer Science, University of Texas at Austin, USA

    Google Scholar 

  • Erikson O, Skyum S (1986) Symmetric distributed termination. In: Rozenberg G, Salomaa A (eds) The book of L. Springer, Berlin Heidelberg New York, pp. 427–430

    Google Scholar 

  • Ferment D (1986) Finite or not finite solutions for the distributed termination problem. Report 86-11, LITP, Universite Paris 7, France

    Google Scholar 

  • Ferment D, Rozoy B (1986) Possibility and impossibility of solutions for the distributed termination problem. Report 86-8, LITP, Universite Paris 7, France

    Google Scholar 

  • Ferment D, Rozoy B (1987) Solutions for the distributed termination problem. In: Albrecht A, Jung H, Mehlhorn K (eds) Parallel algorithms and architectures. Springer, Berlin Heidelberg New York, LNCS 269

    Google Scholar 

  • Hazari C, Zedan H (1987) A distributed algorithm for distributed termination. Inf Process Lett 24:293–297 [It is not the ‘classical’ distributed termination problem: processes are never reactivated. See also Tel G, Van Leeuwen J (1987) Comments on “A distributed algorithm for distributed termination”. Inf Process Lett 25:349]

    Google Scholar 

  • Helary J-M, Jard C, Plouzeau N, Raynal M (1987) Detection of stable properties in distributed applications. Proc 6th ACM Symp Principles Distributed Comput

  • Koo R, Toueg S (1987) Effects of message loss on distributed termination. Tech Rep, Department of Computer Science, Cornell University, USA

    Google Scholar 

  • Lai T-H (1986) Termination detection for dynamic distributed systems with non-first-in-first-out communication. J Parallel and Distributed Computing 3:577–599

    Google Scholar 

  • Lai T-H (1987) Message-optimal algorithms for termination detection in broadcast networks. Department of Computer and Information Science, The Ohio State University, USA

    Google Scholar 

  • Mattern F (1987) Experience with a new distributed termination detection algorithm. In: Gafni E, Raynal M, Santoro N, Van Leeuwen J, Zaks S (eds) Proc 2nd Int Workshop Distributed Algorithms, Amsterdam. Springer, Berlin Heidelberg New York, LNCS

    Google Scholar 

  • Mattern F (1987) An efficient distributed termination test. Report SFB124-32/87, Department of Computer Science, University of Kaiserslautern, FRG

    Google Scholar 

  • Müller H (1987) High level petri nets and distributed termination. In: Voss K, Genrich HJ, Rozenberg G (eds) Concurrency and nets. Springer, Berlin Heidelberg New York, pp 349–362

    Google Scholar 

  • Roucairol G (1987) On the construction of distributed programs. In: Paker Y, Banatre J-P, Bozyigit M (eds) Distributed operating systems: theory and practice. Springer, Berlin Heidelberg New York, pp 47–65

    Google Scholar 

  • Saikkonen H, Ronn S (1986) Distributed termination on a ring. BIT 26:188–194

    Google Scholar 

  • Sanders BA (1987) A method for the construction of probebased termination detection algorithms. Proc IFIP Conf Distributed Processing. North-Holland, Amsterdam New York Oxford

    Google Scholar 

  • Shavit N, Francez N (1986) A new approach to detection of locally indicative stability. In: Kott L (ed) 13th Coll Automata, Lang and Programming. Springer, Berlin Heidelberg New York, LNCS 226, pp 344–358

    Google Scholar 

  • Verjus JP (1987) On the proof of a distributed algorithm. Inf Process Lett 25:145–147

    Google Scholar 

  • Zöbel D (1986) Programmtransformationen zur Ende-Erkennung bei verteilten Berechnungen. Informationstechnik 28 (4):204–213

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, SFB124, University of Kaiserslautern, P. O. Box 3049, D-6750, Kaiserslautern, Federal Republic of Germany

    Friedemann Mattern

Authors
  1. Friedemann Mattern
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Friedemann Matternreceived the Diploma in computer science from the University of Bonn, West Germany, in 1983.He is now a research scientist in the Department of Computer Science at the University of Kaiserslautern and is currently completing his Ph.D. His primary research interests include distributed algorithms, programming language design, and compiler construction. The author can be reached by electronic mail via mattern @ incas.uucp or mattern % uklirb.uucp @ Germany.csne.

This work has been supported by the Deutsche Forschungsgemeinschaft (DFG) as part of the SFB124 research project “VLSI-Design and Parallelism”

Rights and permissions

Reprints and permissions

About this article

Cite this article

Mattern, F. Algorithms for distributed termination detection. Distrib Comput 2, 161–175 (1987). https://doi.org/10.1007/BF01782776

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01782776

Key words

Search

Navigation