License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2017.23
URN: urn:nbn:de:0030-drops-79748
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7974/
Go to the corresponding LIPIcs Volume Portal

Gotsman, Alexey ; Burckhardt, Sebastian

Consistency Models with Global Operation Sequencing and their Composition

pdf-format:
LIPIcs-DISC-2017-23.pdf (0.7 MB)

Abstract

Modern distributed systems often achieve availability and scalability by providing consistency guarantees about the data they manage weaker than linearizability. We consider a class of such consistency models that, despite this weakening, guarantee that clients eventually agree on a global sequence of operations, while seeing a subsequence of this final sequence at any given point of time. Examples of such models include the classical Total Store Order (TSO) and recently proposed dual TSO, Global Sequence Protocol (GSP) and Ordered Sequential Consistency.

We define a unified model, called Global Sequence Consistency (GSC), that has the above models as its special cases, and investigate its key properties. First, we propose a condition under which multiple objects each satisfying GSC can be composed so that the whole set of objects satisfies GSC. Second, we prove an interesting relationship between special cases of GSC - GSP, TSO and dual TSO: we show that clients that do not communicate out-of-band cannot tell the difference between these models. To obtain these results, we propose a novel axiomatic specification of GSC and prove its equivalence to the operational definition of the model.

BibTeX - Entry

@InProceedings{gotsman_et_al:LIPIcs:2017:7974,
  author =	{Alexey Gotsman and Sebastian Burckhardt},
  title =	{{Consistency Models with Global Operation Sequencing and their Composition}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{23:1--23:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Andr{\'e}a W. Richa},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7974},
  URN =		{urn:nbn:de:0030-drops-79748},
  doi =		{10.4230/LIPIcs.DISC.2017.23},
  annote =	{Keywords: Consistency conditions, Weak memory models, Compositionality}
}

Keywords: Consistency conditions, Weak memory models, Compositionality
Collection: 31st International Symposium on Distributed Computing (DISC 2017)
Issue Date: 2017
Date of publication: 12.10.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI