Document Open Access Logo

Robustness against Consistency Models with Atomic Visibility

Authors Giovanni Bernardi, Alexey Gotsman

PDF
Thumbnail PDF

File

LIPIcs.CONCUR.2016.7.pdf
  • Filesize: 0.58 MB
  • 15 pages

Document Identifiers

Author Details

Giovanni Bernardi
Alexey Gotsman

Cite As Get BibTex

Giovanni Bernardi and Alexey Gotsman. Robustness against Consistency Models with Atomic Visibility. In 27th International Conference on Concurrency Theory (CONCUR 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 59, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.CONCUR.2016.7

Abstract

To achieve scalability, modern Internet services often rely on distributed databases with consistency models for transactions weaker than serializability. At present, application programmers often lack techniques to ensure that the weakness of these consistency models does not violate application correctness. We present criteria to check whether applications that rely on a database providing only weak consistency are robust, i.e., behave as if they used a database providing serializability. When this is the case, the application programmer can reap the scalability benefits of weak consistency while being able to easily check the desired correctness properties. Our results handle systematically and uniformly several recently proposed weak consistency models, as well as a mechanism for strengthening consistency in parts of an application.

Subject Classification

Keywords
  • Robustness
  • Replication
  • Consistency models
  • Transactions

Metrics

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

References

  1. D. Abadi. Consistency tradeoffs in modern distributed database system design: CAP is only part of the story. IEEE Computer, 45(2), 2012. Google Scholar
  2. Atul Adya. Weak Consistency: A Generalized Theory and Optimistic Implementations for Distributed Transactions. Ph.D., MIT, Cambridge, MA, USA, March 1999. Google Scholar
  3. M. S. Ardekani, P. Sutra, and M. Shapiro. Non-monotonic snapshot isolation: Scalable and strong consistency for geo-replicated transactional systems. In SRDS, 2013. Google Scholar
  4. P. Bailis, A. Davidson, A. Fekete, A. Ghodsi, Joseph M. Hellerstein, and I. Stoica. Highly Available Transactions: virtues and limitations. In VLDB, 2014. Google Scholar
  5. P. Bailis, A. Fekete, A. Ghodsi, J. M. Hellerstein, and I. Stoica. Scalable atomic visibility with RAMP transactions. In SIGMOD, 2014. Google Scholar
  6. H. Berenson, P. Bernstein, J. Gray, J. Melton, E. O'Neil, and P. O'Neil. A critique of ANSI SQL isolation levels. In SIGMOD, 1995. Google Scholar
  7. G. Bernardi and A. Gotsman. Robustness against consistency models with atomic visibility (extended version). Available from http://software.imdea.org/∼gotsman/. Google Scholar
  8. P. A. Bernstein, V. Hadzilacos, and N. Goodman. Concurrency Control and Recovery in Database Systems. Addison-Wesley, 1987. Google Scholar
  9. A. Bouajjani, E. Derevenetc, and Roland M. Checking and enforcing robustness against TSO. In ESOP, 2013. Google Scholar
  10. S. Burckhardt, D. Leijen, M. Fähndrich, and M. Sagiv. Eventually consistent transactions. In ESOP, 2012. Google Scholar
  11. S. Burckhardt, S. Leijen, J. Protzenko, and M. Fähndrich. Global sequence protocol: A robust abstraction for replicated shared state. In ECOOP, 2015. Google Scholar
  12. A. Cerone, G. Bernardi, and A. Gotsman. A framework for transactional consistency models with atomic visibility. In CONCUR, 2015. Google Scholar
  13. P. Cousot and R. Cousot. Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints. In POPL, 1977. Google Scholar
  14. G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman, A. Pilchin, S. Sivasubramanian, P. Vosshall, and W. Vogels. Dynamo: Amazon’s highly available key-value store. In SOSP, 2007. Google Scholar
  15. A. Fekete. Allocating isolation levels to transactions. In PODS, 2005. Google Scholar
  16. A. Fekete, D. Liarokapis, D. J. O'Neil, P.E O'Neil, and D. Shasha. Making snapshot isolation serializable. ACM Trans. Database Syst., 30(2), 2005. Google Scholar
  17. S. Gilbert and N. Lynch. Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services. ACM SIGACT News, 33(2), 2002. Google Scholar
  18. A. Gotsman, H. Yang, C. Ferreira, M. Najafzadeh, and M. Shapiro. 'Cause I'm strong enough: reasoning about consistency choices in distributed systems. In POPL, 2016. Google Scholar
  19. S. Jorwekar, A. Fekete, K. Ramamritham, and S. Sudarshan. Automating the detection of snapshot isolation anomalies. In VLDB, 2007. Google Scholar
  20. A. Lakshman and P. Malik. Cassandra: A decentralized structured storage system. SIGOPS Oper. Syst. Rev., 44(2), 2010. Google Scholar
  21. K. G. Larsen and B. Thomsen. A modal process logic. In LICS, 1988. Google Scholar
  22. W. Lloyd, M. J. Freedman, M. Kaminsky, and D. G. Andersen. Don't settle for eventual: scalable causal consistency for wide-area storage with COPS. In SOSP, 2011. Google Scholar
  23. S. Lu, A. J. Bernstein, and P. M. Lewis. Correct execution of transactions at different isolation levels. IEEE Trans. Knowl. Data Eng., 16(9), 2004. Google Scholar
  24. Dan R. K. Ports and Kevin Grittner. Serializable snapshot isolation in PostgreSQL. Proc. VLDB Endow., 5(12), August 2012. Google Scholar
  25. M. Sagiv, T. Reps, and R. Wilhelm. Parametric shape analysis via 3-valued logic. ACM Trans. Program. Lang. Syst., 24(3):217-298, 2002. Google Scholar
  26. Y. Sovran, R. Power, M. K. Aguilera, and J. Li. Transactional storage for geo-replicated systems. In SOSP, 2011. Google Scholar
  27. D. Terry, V. Prabhakaran, R. Kotla, M. Balakrishnan, and M. K. Aguilera. Transactions with consistency choices on geo-replicated cloud storage. Technical Report MSR-TR-2013-82, Microsoft Research, 2013. Google Scholar
  28. Kamal Zellag and Bettina Kemme. Consistency anomalies in multi-tier architectures: Automatic detection and prevention. The VLDB Journal, 23(1), 2014. 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