ROLA: A new distributed transaction protocol and its formal analysis

Si Liu, Peter Csaba Ölveczky, Keshav Santhanam, Qi Wang, Indranil Gupta, José Meseguer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Designers of distributed database systems face the choice between stronger consistency guarantees and better performance. A number of applications only require read atomicity (RA) and prevention of lost updates (PLU). Existing distributed database systems that meet these requirements also provide additional stronger consistency guarantees (such as causal consistency), and therefore incur lower performance. In this paper we define a new distributed transaction protocol, ROLA, that targets applications where only RA and PLU are needed. We formally model ROLA in Maude. We then perform model checking to analyze both the correctness and the performance of ROLA. For correctness, we use standard model checking to analyze ROLA’s satisfaction of RA and PLU. To analyze performance we: (a) use statistical model checking to analyze key performance properties; and (b) compare these performance results with those obtained by analyzing in Maude the well-known protocol Walter. Our results show that ROLA outperforms Walter.

Original languageEnglish (US)
Title of host publicationFundamental Approaches to Software Engineering - 21st International Conference, FASE 2018, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2018, Proceedings
EditorsAndy Schurr, Alessandra Russo
PublisherSpringer-Verlag Berlin Heidelberg
Pages77-93
Number of pages17
ISBN (Print)9783319893624
DOIs
StatePublished - Jan 1 2018
Event21st International Conference on Fundamental Approaches to Software Engineering, FASE 2018, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2018 - Thessaloniki, Greece
Duration: Apr 16 2018Apr 20 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10802 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other21st International Conference on Fundamental Approaches to Software Engineering, FASE 2018, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2018
CountryGreece
CityThessaloniki
Period4/16/184/20/18

    Fingerprint

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Liu, S., Ölveczky, P. C., Santhanam, K., Wang, Q., Gupta, I., & Meseguer, J. (2018). ROLA: A new distributed transaction protocol and its formal analysis. In A. Schurr, & A. Russo (Eds.), Fundamental Approaches to Software Engineering - 21st International Conference, FASE 2018, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2018, Proceedings (pp. 77-93). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10802 LNCS). Springer-Verlag Berlin Heidelberg. https://doi.org/10.1007/978-3-319-89363-1_5