Composing and decomposing op-based CRDTs with semidirect products


Resource history | v1 (current) | created by jjones

Details

Composing and decomposing op-based CRDTs with semidirect products

| created by jjones | Add resource "A comprehensive study of Convergent and Commutative Replicated Data Types"
Title
Composing and decomposing op-based CRDTs with semidirect products
Type
Paper
Created
2020-08-02
Description
Operation-based Conflict-free Replicated Data Types (CRDTs) are eventually consistent replicated data types that automatically resolve conflicts between concurrent operations. Op-based CRDTs must be designed differently for each data type, and current designs use ad-hoc techniques to handle concurrent operations that do not naturally commute. We present a new construction, the semidirect product of op-based CRDTs, which combines the operations of two CRDTs into one while handling conflicts between their concurrent operations in a uniform way. We demonstrate the construction's utility by using it to construct novel CRDTs, as well as decomposing several existing CRDTs as semidirect products of simpler CRDTs. Although it reproduces common CRDT semantics, the semidirect product can be viewed as a restricted kind of operational transformation, thus forming a bridge between these two opposing techniques for constructing replicated data types.
Link
https://doi.org/10.1145/3408976
Identifier
no value

authors

This resource has no history of related authors.