Composing and decomposing op-based CRDTs with semidirect products

Resource history | v1 (current) | created by jjones on Mar 11, 2021

Details

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

This resource has no history of related authors.