TY - GEN

T1 - More efficient message-optimal algorithm for distributed termination detection

AU - Lai, Ten Hwang

AU - Tseng, Yu-Chee

AU - Dong, Xuefeng

PY - 1992/12/1

Y1 - 1992/12/1

N2 - Termination detection is a fundamental problem in distributed computing. Many algorithms have been proposed, but only the Chandrasekaran and Venkatesan (CV) algorithm is known to be optimal in worst-case message complexity. This optimal algorithm, however, has several undesirable properties. First, it always requires M′+2*|E|+n-1 control messages, whether it is worst case or best case, where M′ is the number of basic messages issued by the underlying computation after the algorithm starts, |E| is the number of channels in the system, and n is the number of processes. Second, its worst-case detection delay is O(M′). In a message-intensive computation, that might not be tolerable. Third, the maximum amount of space needed by each process is O(M′), a quantity not known at compile time, making it necessary to use the more expensive dynamic memory allocation. Last, it works only for FIFO channels. The purpose of this paper is to remedy these drawbacks, while keeping its strength. We propose an algorithm that requires M′+2(n-1) control messages in the worst case, but much fewer on the average, and in the best case, it uses only 2(n-1) control messages, no matter how large M′ is. The worst-case detection delay is O(n), as compared to the CV-algorithm's O(M′); and the space complexity is Θ(n) for each process, a compile-time known quantity. The algorithm works equally well for both FIFO and Non-FIFO channels.

AB - Termination detection is a fundamental problem in distributed computing. Many algorithms have been proposed, but only the Chandrasekaran and Venkatesan (CV) algorithm is known to be optimal in worst-case message complexity. This optimal algorithm, however, has several undesirable properties. First, it always requires M′+2*|E|+n-1 control messages, whether it is worst case or best case, where M′ is the number of basic messages issued by the underlying computation after the algorithm starts, |E| is the number of channels in the system, and n is the number of processes. Second, its worst-case detection delay is O(M′). In a message-intensive computation, that might not be tolerable. Third, the maximum amount of space needed by each process is O(M′), a quantity not known at compile time, making it necessary to use the more expensive dynamic memory allocation. Last, it works only for FIFO channels. The purpose of this paper is to remedy these drawbacks, while keeping its strength. We propose an algorithm that requires M′+2(n-1) control messages in the worst case, but much fewer on the average, and in the best case, it uses only 2(n-1) control messages, no matter how large M′ is. The worst-case detection delay is O(n), as compared to the CV-algorithm's O(M′); and the space complexity is Θ(n) for each process, a compile-time known quantity. The algorithm works equally well for both FIFO and Non-FIFO channels.

UR - http://www.scopus.com/inward/record.url?scp=0026989603&partnerID=8YFLogxK

U2 - 10.1109/IPPS.1992.222991

DO - 10.1109/IPPS.1992.222991

M3 - Conference contribution

AN - SCOPUS:0026989603

SN - 0818626720

T3 - Proceedings of the International Conference on Parallel Processing

SP - 646

EP - 649

BT - Proceedings of the International Conference on Parallel Processing

PB - Publ by IEEE

Y2 - 23 March 1992 through 26 March 1992

ER -