A family of optimal termination detection algorithms

Springer Science & Business Media
Neeraj Mittal Subbarayan Venkatesan Sathya Peri
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 haveoptimal message complexity. Furthermore, they have optimal detection latency when message ...