A TAXONOMY OF DISTRIBUTED TERMINATION DETECTION ALGORITHMS

An important problem in the field of distributed systems is that of de tecting the termination of a distributed computation. Distributed term ination detection (DTD) is a difficult problem due to the fact that th ere is no simple way of gaining knowledge of the global state of the s ystem. Of the algorithms proposed in the last 15 years, there are many similarities. We have categorized these algorithms based on the follo wing factors: algorithm type (e.g., wave, credit-recovery), required n etwork topology, algorithm symmetry, required process knowledge, commu nication protocol (synchronous or asynchronous), communication channel behavior (first-in first-out (FIFO) or non-FIFO), message optimality, and fault tolerance. This methodology is intended to guide future res earch in DTD algorithms (since research continues on these algorithms) as well as to provide a classification survey for this area. (C) 1998 Elsevier Science Inc. All rights reserved.