Efficient state-based CRDTs by decomposition

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2014

Autores

Almeida, PS (Autor) Outra; Shoker, A (Autor) Outra; Baquero, C (Autor) Outra

Ata de Conferência Internacional

Título: Proceedings of the 1st Workshop on the Principles and Practice of Eventual Consistency, PaPEC 2014

Páginas: 3:1-3:2

1st Workshop on the Principles and Practice of Eventual Consistency, PaPEC 2014

Amsterdam, 13 April 2014 through 13 April 2014

Indexação

Scopus - 1 Citação

Outras Informações

ID Authenticus: P-009-DNS

DOI: 10.1145/2596631.259663

Abstract (EN): Eventual consistency is a relaxed consistency model used in large-scale distributed systems that seek better availability when consistency can be delayed. CRDTs are distributed data types that make eventual consistency of a distributed object possible and non ad-hoc. Specifically, state-based CRDTs achieve this through shipping the entire replica state that is, eventually, merged to other replicas ensuring conver- gence. This imposes a large communication overhead when the replica size or the number of replicas gets larger. In this work, we introduce a decomposable version of state-based CRDTs, called Delta State-based CRDTs (¿-CRDT). A ¿-CRDT is viewed as a join of multiple fine-grained CRDTs of the same type, called deltas (¿). The deltas are produced by applying ¿-mutators, on a replica state, which are mod- ified versions of the original CRDT mutators. This makes it possible to ship small deltas (or batches) instead of ship- ping the entire state. The challenges are to make the join of deltas equivalent to the join of the entire object in clas- sical state-based CRDTs, and to find a way to derive the ¿-mutators. We address this challenge in this work, and we explore the minimal requirements that a communication al- gorithm must offer according to the guarantees provided by the underlying messaging middleware. Copyright © 2007 by the Association for Computing Machinery, Inc.

Idioma: Inglês

Tipo (Avaliação Docente): Científica