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.2018.14
URN: urn:nbn:de:0030-drops-98038
Go to the corresponding LIPIcs Volume Portal

Chockler, Gregory ; Gotsman, Alexey

Multi-Shot Distributed Transaction Commit

LIPIcs-DISC-2018-14.pdf (0.5 MB)


Atomic Commit Problem (ACP) is a single-shot agreement problem similar to consensus, meant to model the properties of transaction commit protocols in fault-prone distributed systems. We argue that ACP is too restrictive to capture the complexities of modern transactional data stores, where commit protocols are integrated with concurrency control, and their executions for different transactions are interdependent. As an alternative, we introduce Transaction Certification Service (TCS), a new formal problem that captures safety guarantees of multi-shot transaction commit protocols with integrated concurrency control. TCS is parameterized by a certification function that can be instantiated to support common isolation levels, such as serializability and snapshot isolation. We then derive a provably correct crash-resilient protocol for implementing TCS through successive refinement. Our protocol achieves a better time complexity than mainstream approaches that layer two-phase commit on top of Paxos-style replication.

BibTeX - Entry

  author =	{Gregory Chockler and Alexey Gotsman},
  title =	{{Multi-Shot Distributed Transaction Commit}},
  booktitle =	{32nd International Symposium on Distributed Computing  (DISC 2018)},
  pages =	{14:1--14:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Ulrich Schmid and Josef Widder},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-98038},
  doi =		{10.4230/LIPIcs.DISC.2018.14},
  annote =	{Keywords: Atomic commit problem, two-phase commit, Paxos}

Keywords: Atomic commit problem, two-phase commit, Paxos
Collection: 32nd International Symposium on Distributed Computing (DISC 2018)
Issue Date: 2018
Date of publication: 04.10.2018

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