DESIGN AND IMPLEMENTATION OF ASYNCHRONOUS TERMINATION DETECTION PROTOCOL IN DISTRIBUTED COMPUTING

Abstract

The problem, of detecting that a distributed algorithm has terminated, is both Important and non-trivial. Even if observation has shown that all the constituent processes of the algorithm are in a passive state, that is, are not active - this cannot be taken as proof that the algorithm as a whole has terminated: for a process observed to be passive may be reactivated by a message from a process that has not yet been observed and which then becomes passive. The problem would be simple if knowledge were available, at any instant, of global state that took into account both the processes and the communication channels. In this dissertation work, a methodology for designing a distributed control mechanism that will recognize the particular state of global stability, that is, of termination has been presented. The termination detection protocol runs in the "session layer" of the network control software without essentially Interfering with or blocking a distributed computation by the network. The protocol presented is completely general, symmetric and distributed in nature and the topology of processors, used for control communication, is a uni-directional Hamiltonian ring. A further improvement in the protocol, causing considerable reduction in the total number of messages required for termination detection, has also been