Document Open Access Logo

Multi-Shot Distributed Transaction Commit

Authors Gregory Chockler, Alexey Gotsman

PDF
Thumbnail PDF

File

LIPIcs.DISC.2018.14.pdf
  • Filesize: 0.53 MB
  • 18 pages

Document Identifiers

Author Details

Gregory Chockler
  • Royal Holloway, University of London, UK
Alexey Gotsman
  • IMDEA Software Institute, Madrid, Spain

Funding

  • Gotsman, Alexey: Alexey Gotsman was supported by an ERC Starting Grant RACCOON.

Cite As Get BibTex

Gregory Chockler and Alexey Gotsman. Multi-Shot Distributed Transaction Commit. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.DISC.2018.14

Abstract

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed computing models
Keywords
  • Atomic commit problem
  • two-phase commit
  • Paxos

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Hal Berenson, Phil Bernstein, Jim Gray, Jim Melton, Elizabeth O'Neil, and Patrick O'Neil. A critique of ANSI SQL isolation levels. In Conference on Management of Data (SIGMOD), 1995. Google Scholar
  2. Philip A Bernstein, Vassos Hadzilacos, and Nathan Goodman. Concurrency Control and Recovery in Database Systems. Addison-Wesley Longman Publishing Co., Inc., 1986. Google Scholar
  3. Andrea J. Borr. Transaction monitoring in ENCOMPASS: reliable distributed transaction processing. In International Conference on Very Large Data Bases (VLDB), 1981. Google Scholar
  4. Miguel Castro and Barbara Liskov. Practical byzantine fault tolerance. In Symposium on Operating Systems Design and Implementation (OSDI), 1999. Google Scholar
  5. Tushar Deepak Chandra, Vassos Hadzilacos, and Sam Toueg. The weakest failure detector for solving consensus. J. ACM, 43(4), 1996. Google Scholar
  6. Bernadette Charron-Bost and André Schiper. Uniform consensus is harder than consensus. J. Algorithms, 51(1), 2004. Google Scholar
  7. Gregory Chockler and Alexey Gotsman. Multi-shot distributed transaction commit (extended version). arXiv CoRR, 1808.00688, 2018. Available from http://arxiv.org/abs/1808.00688. Google Scholar
  8. Paulo R. Coelho, Nicolas Schiper, and Fernando Pedone. Fast atomic multicast. In Conference on Dependable Systems and Networks (DSN), 2017. Google Scholar
  9. James C. Corbett, Jeffrey Dean, Michael Epstein, Andrew Fikes, Christopher Frost, J. J. Furman, Sanjay Ghemawat, Andrey Gubarev, Christopher Heiser, Peter Hochschild, Wilson C. Hsieh, Sebastian Kanthak, Eugene Kogan, Hongyi Li, Alexander Lloyd, Sergey Melnik, David Mwaura, David Nagle, Sean Quinlan, Rajesh Rao, Lindsay Rolig, Yasushi Saito, Michal Szymaniak, Christopher Taylor, Ruth Wang, and Dale Woodford. Spanner: Google’s globally-distributed database. In Symposium on Operating Systems Design and Implementation (OSDI), 2012. Google Scholar
  10. Xavier Défago, André Schiper, and Péter Urbán. Total order broadcast and multicast algorithms: Taxonomy and survey. ACM Comput. Surv., 36(4), 2004. Google Scholar
  11. Aleksandar Dragojević, Dushyanth Narayanan, Edmund B. Nightingale, Matthew Renzelmann, Alex Shamis, Anirudh Badam, and Miguel Castro. No compromises: Distributed transactions with consistency, availability, and performance. In Symposium on Operating Systems Principles (SOSP), 2015. Google Scholar
  12. Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Consensus in the presence of partial synchrony. J. ACM, 35(2), 1988. Google Scholar
  13. Cynthia Dwork and Dale Skeen. The inherent cost of nonblocking commitment. In Symposium on Principles of Distributed Computing (PODC), 1983. Google Scholar
  14. Lisa Glendenning, Ivan Beschastnikh, Arvind Krishnamurthy, and Thomas Anderson. Scalable consistency in Scatter. In Symposium on Operating Systems Principles (SOSP), 2011. Google Scholar
  15. Jim Gray. Notes on data base operating systems. In Operating Systems, An Advanced Course, 1978. Google Scholar
  16. Jim Gray and Leslie Lamport. Consensus on transaction commit. ACM Trans. Database Syst., 31(1), 2006. Google Scholar
  17. Rachid Guerraoui. Revisiting the relationship between non-blocking atomic commitment and consensus. In Workshop on Distributed Algorithms (WDAG), 1995. Google Scholar
  18. Rachid Guerraoui, Mikel Larrea, and André Schiper. Reducing the cost for non-blocking in atomic commitment. In International Conference on Distributed Computing Systems (ICDCS), 1996. Google Scholar
  19. Rachid Guerraoui and Jingjing Wang. How fast can a distributed transaction commit? In Symposium on Principles of Database Systems (PODS), 2017. Google Scholar
  20. V. Hadzilacos. On the relationship between the atomic commitment and consensus problems. In Asilomar Workshop on Fault-Tolerant Distributed Computing, 1990. Google Scholar
  21. Maurice P. Herlihy and Jeannette M. Wing. Linearizability: A correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst., 12(3), 1990. Google Scholar
  22. Flavio Paiva Junqueira, Benjamin C. Reed, and Marco Serafini. Zab: High-performance broadcast for primary-backup systems. In Conference on Dependable Systems and Networks (DSN), 2011. Google Scholar
  23. Idit Keidar and Danny Dolev. Increasing the resilience of atomic commit at no additional cost. In Symposium on Principles of Database Systems (PODS), 1995. Google Scholar
  24. Idit Keidar and Sergio Rajsbaum. A simple proof of the uniform consensus synchronous lower bound. Inf. Process. Lett., 85(1), 2003. Google Scholar
  25. Maciej Kokocinski, Tadeusz Kobus, and Pawel T. Wojciechowski. Make the leader work: Executive deferred update replication. In Symposium on Reliable Distributed Systems (SRDS), 2014. Google Scholar
  26. Tim Kraska, Gene Pang, Michael J. Franklin, Samuel Madden, and Alan Fekete. MDCC: Multi-data center consistency. In European Conference on Computer Systems (EuroSys), 2013. Google Scholar
  27. Leslie Lamport. The part-time parliament. ACM Trans. Comput. Syst., 16(2), 1998. Google Scholar
  28. Hatem Mahmoud, Faisal Nawab, Alexander Pucher, Divyakant Agrawal, and Amr El Abbadi. Low-latency multi-datacenter databases using replicated commit. Proc. VLDB Endow., 6(9), 2013. Google Scholar
  29. Brian M. Oki and Barbara H. Liskov. Viewstamped replication: A new primary copy method to support highly-available distributed systems. In Symposium on Principles of Distributed Computing (PODC), 1988. Google Scholar
  30. Fernando Pedone, Rachid Guerraoui, and André Schiper. The database state machine approach. Distributed and Parallel Databases, 14(1), 2003. Google Scholar
  31. Sebastiano Peluso, Paolo Romano, and Francesco Quaglia. Score: A scalable one-copy serializable partial replication protocol. In International Middleware Conference (Middleware), 2012. Google Scholar
  32. Sebastiano Peluso, Pedro Ruivo, Paolo Romano, Francesco Quaglia, and Luís E. T. Rodrigues. GMU: genuine multiversion update-serializable partial data replication. IEEE Trans. Parallel Distrib. Syst., 27(10), 2016. Google Scholar
  33. K. V. S. Ramarao. Complexity of distributed commit protocols. Acta Informatica, 26(6), 1989. Google Scholar
  34. Masoud Saeida Ardekani, Pierre Sutra, and Marc Shapiro. G-DUR: A middleware for assembling, analyzing, and improving transactional protocols. In International Middleware Conference (Middleware), 2014. Google Scholar
  35. Nicolas Schiper, Pierre Sutra, and Fernando Pedone. P-store: Genuine partial replication in wide area networks. In Symposium on Reliable Distributed Systems (SRDS), 2010. Google Scholar
  36. Fred B. Schneider. Implementing fault-tolerant services using the state machine approach: A tutorial. ACM Comput. Surv., 22(4), 1990. Google Scholar
  37. Daniele Sciascia, Fernando Pedone, and Flavio Junqueira. Scalable deferred update replication. In Conference on Dependable Systems and Networks (DSN), 2012. Google Scholar
  38. Dale Skeen. Nonblocking commit protocols. In Conference on Management of Data (SIGMOD), 1981. Google Scholar
  39. Yair Sovran, Russell Power, Marcos K. Aguilera, and Jinyang Li. Transactional storage for geo-replicated systems. In Symposium on Operating Systems Principles (SOSP), 2011. Google Scholar
  40. Gerhard Weikum and Gottfried Vossen. Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery. Morgan Kaufmann Publishers Inc., 2001. Google Scholar
  41. Irene Zhang, Naveen Kr. Sharma, Adriana Szekeres, Arvind Krishnamurthy, and Dan R. K. Ports. Building consistent transactions with inconsistent replication. In Symposium on Operating Systems Principles (SOSP), 2015. Google Scholar
  42. Irene Zhang, Naveen Kr. Sharma, Adriana Szekeres, Arvind Krishnamurthy, and Dan R. K. Ports. When is operation ordering required in replicated transactional storage? IEEE Data Eng. Bull., 39(1), 2016. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact