From Causal Consistency to Sequential Consistency in Shared Memory Systems

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 : Sequential consistency and causal consistency constitute two of the main consistency criteria used to define the semantics of accesses in the shared memory model. An execution is sequentially consistent if all processes can agree on a same legal sequential history of all the accesses; if processes perceive distinct legal sequential histories of all the accesses, the execution is only causally consistent (legality means that a read does not get an overwritten value). This paper studies synchronization constraints that, when obeyed by operations of a given causally consistent execution, make it sequentially consistent. More precisely, the paper introduces the MSC synchronization (mixed synchronization constraint) which generalizes (1) the known DRF (data race free) and CWF (concurrent write free) synchronizations and (2) a new one called CRF (concurrent read free). The MSC synchronization allows for concurrent conflicting operations on a same object, while ensuring sequential consistency; this is particularly interesting in the the context of distributed systems (where objects are possibly replicated) to cope with partition failures: conflicting operations in two distinct partitions do not necessarily block processes that issue them (as it is the case of quorum based protocols)
Type de document :
[Research Report] RR-2557, INRIA. 1995
Liste complète des métadonnées
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 14:33:56
Dernière modification le : vendredi 16 novembre 2018 - 01:24:27
Document(s) archivé(s) le : lundi 5 avril 2010 - 00:05:35



  • HAL Id : inria-00074123, version 1


Michel Raynal, André Schiper. From Causal Consistency to Sequential Consistency in Shared Memory Systems. [Research Report] RR-2557, INRIA. 1995. 〈inria-00074123〉



Consultations de la notice


Téléchargements de fichiers