Ring based termination detection algorithm for distributed computations (Q1124323)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Ring based termination detection algorithm for distributed computations |
scientific article |
Statements
Ring based termination detection algorithm for distributed computations (English)
0 references
1988
0 references
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).
0 references
concurrency
0 references
distributed program
0 references
communicating sequential processes
0 references