Detecting termination of distributed computations using markers

ABSTRACT

A problem of considerable importance in designing computations by process networks, is detection of termination. We propose a very simple algorithm for termination detection in an arbitrary network using a single marker We show an application of this scheme in solving the problem of token loss detection and token regeneration in a token ring.

REFERENCES

• 1: Gouda, M. "Personal Communication," Department of Computer Sciences, University of Texas, Austin, Texas 78712.
• 2: Dijkstra, E.W. and Scholten, C.S., "Termination Detection for Diffusing Computations," Information Processing Letters, 11, 1 (Aug. 1980), pp. 1-4.
• 3: Dijkstra, E.W., "Distributed Termination Detection Revisited," EWD 828, Plataanstraat 5, 5671 AL Nuenen, The Netherlands.
• 4: 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 [doi>10.1145/800220.806678]
• 5: Jayadev Misra , K. M. Chandy, A Distributed Graph Algorithm: Knot Detection, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.4, p.678-686, Oct. 1982 [doi>10.1145/69622.357190]
• 6: K. Mani Chandy , J. Misra, Distributed computation on graphs: shortest path algorithms, Communications of the ACM, v.25 n.11, p.833-837, Nov 1982 [doi>10.1145/358690.358717]
• 7: 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 [doi>10.1145/357153.357156]
• 8: K. Mani Chandy , Jayadev Misra , Laura M. Haas, Distributed deadlock detection, ACM Transactions on Computer Systems (TOCS), v.1 n.2, p.144-156, May 1983 [doi>10.1145/357360.357365]
• 9: Nissim Francez, Distributed Termination, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.1, p.42-55, Jan. 1980 [doi>10.1145/357084.357087]
• 10: Chandy, K.M. and Lamport, Leslie, "Detecting Stability in Distributed Systems," in preparation.
• 11: N. Frances , Michael Rodeh , Michel Sintzoff, Distributed Termination with Interval Assertions, Proceedings of the International Colloquium on Formalization of Programming Concepts, p.280-291, April 19-25, 1981
• 12: Francez, N. and Rodeh, M., "Achieving Distributed Termination Without Freezing," IEEE-TSE, Vol. SE-8, No. 3, May 1982, pp. 287-292.
• 13: Le Lann, Gerard, "Distributed Systems - Towards a Formal Approach," Information Processing 77, B. Gilchrist, Editor, IFIP, North-Holland Publishing Company (1977).
• 14: Kumar, Devendra, Ph.D. Thesis (in preparation), Computer Sciences Department, University of Texas, Austin, 78712.
• 15: K. M. Chandy , J. Misra, Asynchronous distributed simulation via a sequence of parallel computations, Communications of the ACM, v.24 n.4, p.198-206, April 1981 [doi>10.1145/358598.358613]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Token rings

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

General Terms:
Algorithms