Thumbnail
Access Restriction
Open

Author Almeida, Paulo Sérgio ♦ Shoker, Ali ♦ Baquero, Carlos ♦ Tec, Haslab Inesc
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Efficient State-based Crdts ♦ Incremental Nature ♦ Small Message ♦ Commutative Join Operation ♦ Causal Consistency ♦ Eventual Consistency ♦ Local State ♦ Large Communication Overhead ♦ Crdt Specification ♦ State-based Crdts Achieve ♦ Current State-based Crdts ♦ Traditional State-based Crdts ♦ Eventual Convergence ♦ State Size Becomes ♦ Local State Change ♦ Data Type ♦ Full State ♦ Remote State ♦ Well-known Replicated Datatypes ♦ Delta State Conflict-free Replicated Datatypes ♦ Anti-entropy Algorithm ♦ Distributed Object ♦ Basic One ♦ Crdt Framework ♦ Non Ad-hoc ♦ Entire State ♦ Unreliable Communication Channel ♦ Operation-based Crdts
Abstract CRDTs are distributed data types that make eventual consistency of a distributed object possible and non ad-hoc. Specifically, state-based CRDTs achieve this by sharing local state changes through shipping the entire state, that is then merged to other replicas with an idempotent, associative, and commutative join operation, ensuring convergence. This imposes a large communication overhead as the state size becomes larger. We introduce Delta State Conflict-Free Replicated Datatypes (δ-CRDT), which make use of δ-mutators, defined in such a way to return a delta-state, typically, with a much smaller size than the full state. Delta-states are joined to the local state as well as to the remote states (after being shipped). This can achieve the best of both worlds: small messages with an incremental nature, as in operation-based CRDTs, disseminated over unreliable communication channels, as in traditional state-based CRDTs. We introduce the δ-CRDT framework, and we explain it through establishing a correspondence to current state-based CRDTs. In addition, we present two anti-entropy algorithms: a basic one that provides eventual convergence, and another one that ensures both convergence and causal consistency. We also introduce two δ-CRDT specifications of well-known replicated datatypes.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Publisher Date 2014-01-01