Experience with a new distributed termination detection algorithm. (English) Zbl 0648.68036

Distributed algorithms, Proc. 2nd Int. Workshop, Amsterdam/Neth. 1987, Lect. Notes Comput. Sci. 312, 127-143 (1988).
[For the entire collection see Zbl 0638.00039.]
A termination detection algorithm for a general model of distributed computations where processes communicate over asynchronous non-FIFO channels is presented. It has O(mn) message complexity if the control network is a ring, a (spanning) tree, or a general undirected graph and O(m) message complexity on star networks and complete networks. Several variants of the basic principle are discussed, one of which is a symmetric version where any process can start the algorithm independently from the other processes.
Preliminary experimental results show that far less control messages than indicated by the worst case behavior are usually generated. In a distributed puzzle-solving system and used as a test application only about \(\sqrt{m}\) control messages have been counted. The constraint based puzzle-solving method is explained and several test cases are reported.


68N25 Theory of operating systems
68Q25 Analysis of algorithms and problem complexity


Zbl 0638.00039