research-article

Making operation-based CRDTs operation-based

Authors:

Carlos Baquero,

Paulo Sérgio Almeida,

Ali ShokerAuthors Info & Claims

PaPEC '14: Proceedings of the First Workshop on Principles and Practice of Eventual Consistency

Article No.: 7, Pages 1 - 2

https://doi.org/10.1145/2596631.2596632

Published: 13 April 2014 Publication History

Get Access

Abstract

Conflict-free Replicated Datatypes can simplify the design of predictable eventual consistency. They can be classified into state-based or operation-based. Operation-based approaches have the potential for allowing compact designs in both the sent message and the object state size, but current approaches are still far from this objective. Here we explore the design space for operation-based solutions, and we leverage the interaction with the middleware by offering a technique that delivers very compact solutions, while only broadcasting operation names and arguments.

References

[1]

P. Bailis and A. Ghodsi. Eventual consistency today: Limitations, extensions, and beyond. Queue, 11(3):20:20--20:32, Mar. 2013.

Digital Library

Google Scholar

[2]

K. P. Birman and T. A. Joseph. Reliable communication in the presence of failures. Trans. on Computer Systems, 5(1):47--76, Feb. 1987.

Digital Library

Google Scholar

[3]

S. Cribbs and R. Brown. Data structures in Riak. In Riak Conference (RICON), San Francisco, CA, USA, oct 2012.

Google Scholar

[4]

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 Symp. on Op. Sys. Principles (SOSP), volume 41 of Operating Systems Review, pages 205--220, Stevenson, Washington, USA, Oct. 2007. Assoc. for Computing Machinery.

Digital Library

Google Scholar

[5]

S. Gilbert and N. Lynch. Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services. SIGACT News, 33(2):51--59, 2002.

Digital Library

Google Scholar

[6]

R. A. Golding. Weak-consistency group communication and membership. PhD thesis, University of California Santa Cruz, Santa Cruz, CA, USA, Dec. 1992. Tech. Report no. UCSC-CRL-92-52.

Digital Library

Google Scholar

[7]

P. Mahajan, L. Alvisi, and M. Dahlin. Consistency, availability, and convergence. Technical Report UTCS TR-11-22, Dept. of Comp. Sc., The U. of Texas at Austin, Austin, TX, USA, 2011.

Google Scholar

[8]

M. Shapiro, N. Preguiça, C. Baquero, and M. Zawirski. A comprehensive study of Convergent and Commutative Replicated Data Types. Rapp. Rech. 7506, Institut National de la Recherche en Informatique et Automatique (INRIA), Rocquencourt, France, Jan. 2011.

Google Scholar

[9]

M. Shapiro, N. Preguiça, C. Baquero, and M. Zawirski. Conflict-free replicated data types. In X. Défago, F. Petit, and V. Villain, editors, Int. Symp. on Stabilization, Safety, and Security of Distributed Systems (SSS), volume 6976 of Lecture Notes in Comp. Sc., pages 386--400, Grenoble, France, Oct. 2011. Springer-Verlag.

Digital Library

Google Scholar

[10]

W. Vogels. Eventually consistent. ACM Queue, 6(6):14--19, Oct. 2008.

Digital Library

Google Scholar

Cited By

View all

Nieto AGondelman LReynaud ATimany ABirkedal L(2022)Modular verification of op-based CRDTs in separation logicProceedings of the ACM on Programming Languages10.1145/35633516:OOPSLA2(1788-1816)Online publication date: 31-Oct-2022
https://dl.acm.org/doi/10.1145/3563351
Mao YLiu ZJacobsen HBellavista PZhang KGherbi ABagchi SPatiño MDi Modica GGascon-Samson J(2022)Reversible conflict-free replicated data typesProceedings of the 23rd ACM/IFIP International Middleware Conference10.1145/3528535.3565252(295-307)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1145/3528535.3565252
Brocco ASzekeres ASivaramakrishnan K(2022)MeldaProceedings of the 9th Workshop on Principles and Practice of Consistency for Distributed Data10.1145/3517209.3524039(1-7)Online publication date: 5-Apr-2022
https://dl.acm.org/doi/10.1145/3517209.3524039
Show More Cited By

Index Terms

Making operation-based CRDTs operation-based
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
        Data types and structures
2. Theory of computation
  1. Models of computation
    1. Concurrency
      1. Parallel computing models

Recommendations

Making CRDTs Byzantine fault tolerant
PaPoC '22: Proceedings of the 9th Workshop on Principles and Practice of Consistency for Distributed Data

It is often claimed that Conflict-free Replicated Data Types (CRDTs) ensure consistency of replicated data in peer-to-peer systems. However, peer-to-peer systems usually consist of untrusted nodes that may deviate from the specified protocol (i.e. ...
Making Operation-Based CRDTs Operation-Based
Proceedings of the 14th IFIP WG 6.1 International Conference on Distributed Applications and Interoperable Systems - Volume 8460

Conflict-free Replicated Datatypes CRDT are usually classified as either state-based or operation-based. However, the standard definition of op-based CRDTs is very encompassing, allowing even sending the full-state, blurring the distinction. We ...
Improving the Reactivity of Pure Operation-Based CRDTs
PaPoC '21: Proceedings of the 8th Workshop on Principles and Practice of Consistency for Distributed Data

Modern distributed applications increasingly replicate data to guarantee both high availability of the system and an optimal user experience. Conflict-Free Replicated Data Types (CRDTs) are a family of data types specially designed for highly available ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PaPEC '14: Proceedings of the First Workshop on Principles and Practice of Eventual Consistency

April 2014

47 pages

ISBN:9781450327169

DOI:10.1145/2596631

Program Chair:
Marc Shapiro
INRIA, LIP6

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 April 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

North Portugal Regional Operational Program under National Strategic Reference Framework (NSRF), through European Regional Development Fund (ERDF)
Seventh Framework Programme

Conference

EuroSys 2014

Sponsor:

SIGOPS

EuroSys 2014: Ninth Eurosys Conference 2014

April 13, 2014

Amsterdam, The Netherlands

Acceptance Rates

PaPEC '14 Paper Acceptance Rate 16 of 20 submissions, 80%;

Overall Acceptance Rate 16 of 20 submissions, 80%

Upcoming Conference

EuroSys '25

Sponsor:
sigops

Twentieth European Conference on Computer Systems

March 30 - April 3, 2025

Rotterdam , Netherlands

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
268
Total Downloads

Downloads (Last 12 months)20
Downloads (Last 6 weeks)4

Reflects downloads up to 17 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Nieto AGondelman LReynaud ATimany ABirkedal L(2022)Modular verification of op-based CRDTs in separation logicProceedings of the ACM on Programming Languages10.1145/35633516:OOPSLA2(1788-1816)Online publication date: 31-Oct-2022
https://dl.acm.org/doi/10.1145/3563351
Mao YLiu ZJacobsen HBellavista PZhang KGherbi ABagchi SPatiño MDi Modica GGascon-Samson J(2022)Reversible conflict-free replicated data typesProceedings of the 23rd ACM/IFIP International Middleware Conference10.1145/3528535.3565252(295-307)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1145/3528535.3565252
Brocco ASzekeres ASivaramakrishnan K(2022)MeldaProceedings of the 9th Workshop on Principles and Practice of Consistency for Distributed Data10.1145/3517209.3524039(1-7)Online publication date: 5-Apr-2022
https://dl.acm.org/doi/10.1145/3517209.3524039
Nicolas MOster GPerrin O(2022)Efficient Renaming in Sequence CRDTsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2022.317257033:12(3870-3885)Online publication date: 1-Dec-2022
https://doi.org/10.1109/TPDS.2022.3172570
Kleppmann MMulligan DGomes VBeresford A(2022)A Highly-Available Move Operation for Replicated TreesIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2021.311860333:7(1711-1724)Online publication date: 1-Jul-2022
https://doi.org/10.1109/TPDS.2021.3118603
Anjana PChandrassery APeri S(2022)An Efficient Approach to Move Elements in a Distributed Geo-Replicated Tree2022 IEEE 15th International Conference on Cloud Computing (CLOUD)10.1109/CLOUD55607.2022.00071(479-488)Online publication date: Jul-2022
https://doi.org/10.1109/CLOUD55607.2022.00071
Preguiça NBaquero CShapiro M(2022)Conflict-Free Replicated Data Types (CRDTs)Encyclopedia of Big Data Technologies10.1007/978-3-319-63962-8_185-2(1-10)Online publication date: 17-May-2022
https://doi.org/10.1007/978-3-319-63962-8_185-2
Brocco A(2021)Delta-State JSON CRDT: Putting Collaboration on Solid GroundStabilization, Safety, and Security of Distributed Systems10.1007/978-3-030-91081-5_32(474-478)Online publication date: 9-Nov-2021
https://doi.org/10.1007/978-3-030-91081-5_32
Preguiça NBaquero CShapiro M(2019)Conflict-Free Replicated Data Types CRDTsEncyclopedia of Big Data Technologies10.1007/978-3-319-77525-8_185(491-500)Online publication date: 20-Feb-2019
https://doi.org/10.1007/978-3-319-77525-8_185
Dabaghchian MRakamaric ZOzkan BMutlu ETasiran S(2018)Consistency-Aware Scheduling for Weakly Consistent ProgramsACM SIGSOFT Software Engineering Notes10.1145/3149485.314949342:4(1-5)Online publication date: 11-Jan-2018
https://dl.acm.org/doi/10.1145/3149485.3149493
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Making CRDTs Byzantine fault tolerant

Making Operation-Based CRDTs Operation-Based

Improving the Reactivity of Pure Operation-Based CRDTs