Efficient Distributed Detection of Conjunctions of Local Predicates

Abstract : Global predicate detection is a fundamental problem in distributed systems and finds applications in many domains such as testing and debugging distributed programs. This paper presents two efficient distributed algorithms to detect conjunctive form global predicates in distributed systems. The algorithms detect the first consistent global state that satisfies the predicate even if the predicate is unstable. The algorithms are based on complementary approaches and are dual of each other. The algorithms are distributed because the predicate detection efforts as well as the necessary information is equally distributed among the processes. We prove the correctness of the algorithms and compare their performance with those of the existing predicate detection algorithms. The proposed algorithms compare very favorably with the existing algorithms in terms of the number of messages exchanged for predicate detection.
Type de document :
Rapport
[Research Report] RR-2731, INRIA. 1995
Liste complète des métadonnées

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

Fichiers

Identifiants

  • HAL Id : inria-00073963, version 1

Collections

Citation

Michel Hurfin, Masaaki Mizuno, Michel Raynal, Mukesh Singhal. Efficient Distributed Detection of Conjunctions of Local Predicates. [Research Report] RR-2731, INRIA. 1995. 〈inria-00073963〉

Partager

Métriques

Consultations de la notice

194

Téléchargements de fichiers

119