(1) Department of Computer Science, The University of Texas at Dallas, Richardson, TX 75083, USA
Abstract:
An important problem in distributed systems is to detect termination of a distributed computation. A computation is said to
have terminated when all processes have become passive and all channels have become empty. In this paper, we present a suite
of algorithms for detecting termination of a non-diffusing computation for an arbitrary communication topology under a variety
of conditions. All our termination detection algorithms have optimal message complexity. Furthermore, they have optimal detection latency when message processing time is ignored.
A preliminary version of the paper first appeared in the 18th Symposium on Distributed Computing (DISC), 2004 27].