Termination detection in a very general distributed computing model
Jerzy Brzeziński, Jean-Michel Hélary, Michel Raynal · 2002
Termination detection constitutes one of the basic problems of distributed computing, and many distributed algorithms have been proposed to solve it, but all these algorithms consider a very simple model for the underlying application programs: for processes of such programs, nondeterministic constructs are allowed, but each 'receive' statement (request) concerns only one message at a time. A more realistic and very general model of distributed computing is first presented, allowing a request to be atomic on several messages and to obey AND/OR/AND-OR/k-out-of-n/etc. request types. Within this framework, two definitions of termination are proposed and discussed. Then, accordingly, two distributed algorithms for detecting these terminations are presented and evaluated; they differ in the information they use and in the time they need to claim termination.>