Distributed termination detection : General model and algorithms

Jerzy Brzezinski 1 Jean-Michel Hélary 2 Michel Raynal 2
2 ADP - Distributed Algorithms and Protocols
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, INRIA Rennes
Abstract : Termination detection constitutes one of the basic problems of distributed computing and many distributed algorithms have been proposed to solve it. These algorithms differ in the way they ensure consistency of the detection and in the assumptions they do concerning behaviour of channels (FIFO or not, bounded delay or asynchronous, etc.) But all these algorithms consider a very simple model for underlying application programs : for processes of such programs non-deterministic constructs are allowed but each receive statement (request) concerns only one message at a time. In this paper a more realistic and very general model of distributed computing is first presented. This model allows a request (receive statement) to be atomic on several messages and to obey and/or/and-or/k out of n/etc request types. These types are abstracted by the notion of an activation condition. Within this framework two definitions of termination are proposed and discussed. Then, accordingly, two distributed algorithms to detect these terminations are presented and evaluated, they differ in the information they use and in the time they need to claim termination.
Type de document :
Rapport
[Research Report] RR-1964, INRIA. 1993
Liste complète des métadonnées

Littérature citée [6 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00074709
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 16:07:00
Dernière modification le : jeudi 11 janvier 2018 - 06:20:08
Document(s) archivé(s) le : lundi 5 avril 2010 - 00:13:51

Fichiers

Identifiants

  • HAL Id : inria-00074709, version 1

Collections

Citation

Jerzy Brzezinski, Jean-Michel Hélary, Michel Raynal. Distributed termination detection : General model and algorithms. [Research Report] RR-1964, INRIA. 1993. 〈inria-00074709〉

Partager

Métriques

Consultations de la notice

234

Téléchargements de fichiers

1138