Please use this identifier to cite or link to this item: http://repositorio.inesctec.pt/handle/123456789/4204
Title: Efficient state-based CRDTs by decomposition
Authors: Paulo Sérgio Almeida
Ali Shoker
Carlos Baquero
Issue Date: 2014
Abstract: 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 (d-CRDT). A d-CRDT is viewed as a join of multiple fine-grained CRDTs of the same type, called deltas (d). The deltas are produced by applying d-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 d-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.
URI: http://repositorio.inesctec.pt/handle/123456789/4204
http://dx.doi.org/10.1145/2596631.259663
metadata.dc.type: conferenceObject
Publication
Appears in Collections:HASLab - Articles in International Conferences

Files in This Item:
File Description SizeFormat 
P-009-DNS.pdf116.31 kBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.