¡@

An important problem in distributed systems is to detect termination of a distributed computation. A distributed computation is said to have terminated when all processes have become passive and all channels have become empty. We focus on two attributes of a termination detection algorithm. First, whether the distributed computation starts from a single process or from multiple processes: diffusing computation versus non-diffusing computation. Second, whether the detection algorithm should be initiated along with the computation or can be initiated any time after the computation has started: simultaneous initiation versus delayed initiation. We show that any termination detection algorithm for a diffusing computation can be transformed into a termination detection algorithm for a non-diffusing computation. We also demonstrate that any termination detection algorithm for simultaneous initiation can be transformed into a termination detection algorithm for delayed initiation. We prove the correctness of our transformations, and show that our transformations have only a small impact on the performance of the given termination detection algorithm.

Keywords: distributed system, termination detection, algorithm transformation, diffusing and non-diffusing computations, simultaneous and delayed initiations, worst-case and average-case message complexities, fault-tolerance

Retrieve PDF document (200801_11.pdf)

Received December 5, 2005; revised September 13, 2006; accepted November 1, 2006.
Communicated by Tsan-sheng Hsu.
^*A preliminary version of the paper has appeared earlier in the 2004 Proceedings of the ISCA International Conference on Parallel and Distributed Computing Systems (PDCS).