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.CONCUR.2015.58
URN: urn:nbn:de:0030-drops-53756
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5375/
Go to the corresponding LIPIcs Volume Portal

Cerone, Andrea ; Bernardi, Giovanni ; Gotsman, Alexey

A Framework for Transactional Consistency Models with Atomic Visibility

pdf-format:
15.pdf (0.7 MB)

Abstract

Modern distributed systems often rely on databases that achieve scalability by providing only weak guarantees about the consistency of distributed transaction processing. The semantics of programs interacting with such a database depends on its consistency model, defining these guarantees. Unfortunately, consistency models are usually stated informally or using disparate formalisms, often tied to the database internals. To deal with this problem, we propose a framework for specifying a variety of consistency models for transactions uniformly and declaratively. Our specifications are given in the style of weak memory models, using structures of events and relations on them. The specifications are particularly concise because they exploit the property of atomic visibility guaranteed by many consistency models: either all or none of the updates by a transaction can be visible to another one. This allows the specifications to abstract from individual events inside transactions. We illustrate the use of our framework by specifying several existing consistency models. To validate our specifications, we prove that they are equivalent to alternative operational ones, given as algorithms closer to actual implementations. Our work provides a rigorous foundation for developing the metatheory of the novel form of concurrency arising in weakly consistent large-scale databases.

BibTeX - Entry

@InProceedings{cerone_et_al:LIPIcs:2015:5375,
  author =	{Andrea Cerone and Giovanni Bernardi and Alexey Gotsman},
  title =	{{A Framework for Transactional Consistency Models with Atomic Visibility}},
  booktitle =	{26th International Conference on Concurrency Theory (CONCUR 2015)},
  pages =	{58--71},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-91-0},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{42},
  editor =	{Luca Aceto and David de Frutos Escrig},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5375},
  URN =		{urn:nbn:de:0030-drops-53756},
  doi =		{10.4230/LIPIcs.CONCUR.2015.58},
  annote =	{Keywords: Replication, Consistency models, Transactions}
}

Keywords: Replication, Consistency models, Transactions
Collection: 26th International Conference on Concurrency Theory (CONCUR 2015)
Issue Date: 2015
Date of publication: 26.08.2015

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