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
Loading...
Thumbnail Image
Name

RS95.ps

Access type

openaccess

Size

143.17 KB

Format

Postscript

Checksum (MD5)

2b2b29cda00ed8d0671ec3615da5d08d

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