An Alternate representation of distributed computations

Celine Valot Dominique Fortin 1
1 ARCHI - Architecture
INRIA Rocquencourt
Abstract : This paper proposes another representation of the event partially ordered set of distributed executions which relies on diagrams called arc diagrams. Arc diagrams are already in use within order theory and appears to have useful properties which can be of interest to distributed algorithms. It is shown that arc diagrams describe efficiently event ordering relations as well as reachable global states. Access to both of those levels is done without switching between different representations. Furthermore, this representation allows to decompose the event set into chains and yields to nearly optimal linear extensions. These linear extensions can beviewed as the nearest linear extensions of the poset that ca be produced. Those can be efficiently used to detect a new kind of global predicates called greedy predicates.
Type de document :
[Research Report] RR-1944, INRIA. 1993
Liste complète des métadonnées
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 16:11:37
Dernière modification le : vendredi 16 septembre 2016 - 15:13:22
Document(s) archivé(s) le : mardi 12 avril 2011 - 18:39:43



  • HAL Id : inria-00074730, version 1



Celine Valot, Dominique Fortin. An Alternate representation of distributed computations. [Research Report] RR-1944, INRIA. 1993. 〈inria-00074730〉



Consultations de la notice


Téléchargements de fichiers