The Minimal Dependency Relation for Causal Event Ordering in Distributed Computing - LAAS-Réseaux et Communications Accéder directement au contenu
Article Dans Une Revue Applied Mathematics & Information Sciences Année : 2015

The Minimal Dependency Relation for Causal Event Ordering in Distributed Computing

Résumé

Several algorithms of different domains in distributed systems are designed over the principle of the Happened-Before Relation (HBR). One common as-pect among them is that they intend to be efficient in their implementation by identifying and ensuring the necessary and sufficient dependency constraints. In this pursuit, some previous works talk about the use of a transitive reduction of the causality. However, none of these works formally prove in a broad manner that such transitive reduction is the minimal expression of the HBR. In this pa-per, a formal study of the minimal binary relation (transitive reduction) of the HBR is presented, which is called the Immediate Dependency Relation (IDR). The study shows that since the transitive closure of the HBR is antisymmetric and finite, it implies that the IDR is unique. This is important because it means that all of the works that deal with a minimal expression of the HBR discuss the same minimal binary relation. In addition, an extension to the IDR to iden-tify causal immediate dependencies only among a subset of relevant events is presented. Finally, as case of study, the extension of the IDR is applied to the causal delivery of messages.
Fichier principal
Vignette du fichier
IDR_27_jun_2012.pdf (137.08 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01096635 , version 1 (17-12-2014)

Identifiants

Citer

Saúl Eduardo Pomares Hernández. The Minimal Dependency Relation for Causal Event Ordering in Distributed Computing. Applied Mathematics & Information Sciences, 2015, 9 (1), pp.57-61. ⟨10.12785/amis/090108⟩. ⟨hal-01096635⟩
179 Consultations
344 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More