From Causal Consistency to Sequential Consistency in Shared Memory Systems - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1995

From Causal Consistency to Sequential Consistency in Shared Memory Systems

Résumé

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)

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-2557.pdf (324.91 Ko) Télécharger le fichier

Dates et versions

inria-00074123 , version 1 (24-05-2006)

Identifiants

  • HAL Id : inria-00074123 , version 1

Citer

Michel Raynal, André Schiper. From Causal Consistency to Sequential Consistency in Shared Memory Systems. [Research Report] RR-2557, INRIA. 1995. ⟨inria-00074123⟩
301 Consultations
1430 Téléchargements

Partager

Gmail Facebook X LinkedIn More