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.ECOOP.2020.21
URN: urn:nbn:de:0030-drops-131782
URL: https://drops.dagstuhl.de/opus/volltexte/2020/13178/
Go to the corresponding LIPIcs Volume Portal


Xiong, Shale ; Cerone, Andrea ; Raad, Azalea ; Gardner, Philippa

Data Consistency in Transactional Storage Systems: A Centralised Semantics

pdf-format:
LIPIcs-ECOOP-2020-21.pdf (0.8 MB)


Abstract

We introduce an interleaving operational semantics for describing the client-observable behaviour of atomic transactions on distributed key-value stores. Our semantics builds on abstract states comprising centralised, global key-value stores and partial client views. Using our abstract states, we present operational definitions of well-known consistency models in the literature, and prove them to be equivalent to their existing declarative definitions using abstract executions. We explore two applications of our operational framework: 1) verifying that the COPS replicated database and the Clock-SI partitioned database satisfy their consistency models using trace refinement, and 2) proving invariant properties of client programs.

BibTeX - Entry

@InProceedings{xiong_et_al:LIPIcs:2020:13178,
  author =	{Shale Xiong and Andrea Cerone and Azalea Raad and Philippa Gardner},
  title =	{{Data Consistency in Transactional Storage Systems: A Centralised Semantics}},
  booktitle =	{34th European Conference on Object-Oriented Programming (ECOOP 2020)},
  pages =	{21:1--21:31},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-154-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{166},
  editor =	{Robert Hirschfeld and Tobias Pape},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13178},
  URN =		{urn:nbn:de:0030-drops-131782},
  doi =		{10.4230/LIPIcs.ECOOP.2020.21},
  annote =	{Keywords: Operational Semantics, Consistency Models, Transactions, Distributed Key-value Stores}
}

Keywords: Operational Semantics, Consistency Models, Transactions, Distributed Key-value Stores
Collection: 34th European Conference on Object-Oriented Programming (ECOOP 2020)
Issue Date: 2020
Date of publication: 06.11.2020


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