Ring based termination detection algorithm for distributed computations (Q1124323)

Let a distributed program P consists of n communicating sequential processes \(p_ 1,p_ 1,...,p_ n\). Each process \(p_ i\) has a local termination condition \(B_ i\) and let GTC \(=\) \(\bigwedge^{n}_{i=1}B_ i\) denote the global termination condition. A fully symmetric algorithm for detecting \(GTC=true\) (by at least one process) is proposed. This detection is realized by message passing (special control communications, apart from basic communications), the processes of P being connected by a Hamiltonian ring (each process knows only its successor in the ring). The algorithm is simpler than that of \textit{R. K. Arora}, \textit{S. P. Ranna}, \textit{M. N. Gupta} [Ring based detection algorithm for distributed computations, Microprocessing and Microprogramming 19(3), 219-226 (1987)] or \textit{S. P. Ranna} [Inf. Process. Lett. 17(1), 1-4 (1983)], taking a smaller number of messages to detect GTC (in averages cases).