Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. From Causal Consistency to Sequential Consistency in Shared Memory Systems
 
conference paper

From Causal Consistency to Sequential Consistency in Shared Memory Systems

Raynal, M.
•
Schiper, A.  
1995
Foundations of Software Technology and Theoretical Computer Science. FSTTCS 1995
15th Conference on Foundations of Software Technologies and Theoretical Computer Science

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 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). Technically, a tag (control type) is associated with each operation, and all operations endowed with the same tag obey the same synchronization constraint.

  • Files
  • Details
  • Metrics
Type
conference paper
DOI
10.1007/3-540-60692-0_48
Author(s)
Raynal, M.
Schiper, A.  
Date Issued

1995

Publisher

Springer-Verlag

Published in
Foundations of Software Technology and Theoretical Computer Science. FSTTCS 1995
Start page

180

End page

194

Written at

EPFL

EPFL units
LSR-IC  
Event nameEvent placeEvent date
15th Conference on Foundations of Software Technologies and Theoretical Computer Science

Bangalore, India

December 18–20, 1995

Available on Infoscience
May 20, 2005
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/213896
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés