The causal ordering abstraction and a simple way to implement it

Michel Raynal 1 André Schiper 2
1 ADP - Distributed Algorithms and Protocols
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, INRIA Rennes
Abstract : Control in distributed systems is mainly introduced to reduce non-determinism. This non-determinism is due on once hand to the asynchronous execution of the processes located on the various sites of the system, and on the other hand to the asynchronous nature of the communication channels. In order to get rid of part of the asynchronism due to the communication channels, a new ordering relation, known as causal ordering, has been introduced by Birman. After having shown the usefulness of causal ordering, we propose a natural implementation, based simply on counting the emitted messages. A proof of the correctness of the algorithm is also given.
Type de document :
[Research Report] RR-1132, INRIA. 1989
Liste complète des métadonnées
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 18:11:36
Dernière modification le : vendredi 16 novembre 2018 - 01:29:41
Document(s) archivé(s) le : mardi 12 avril 2011 - 23:06:50



  • HAL Id : inria-00075427, version 1


Michel Raynal, André Schiper. The causal ordering abstraction and a simple way to implement it. [Research Report] RR-1132, INRIA. 1989. 〈inria-00075427〉



Consultations de la notice


Téléchargements de fichiers