Skip to Main content Skip to Navigation
New interface
Conference papers

Making Operation-Based CRDTs Operation-Based

Abstract : Conflict-free Replicated Datatypes (CRDT) are usually classified as either state-based or operation-based. However, the standard definition of op-based CRDTs is very encompassing, allowing even sending the full-state, blurring the distinction. We introduce pure op-based CRDTs, that can only send operations to other replicas, drawing a clear distinction from state-based ones. Datatypes with commutative operations can be trivially implemented as pure op-based CRDTs using standard reliable causal delivery. We propose an extended API – tagged reliable causal broadcast – that provides causality information upon delivery, and show how it can be used to also implement other datatypes having non-commutative operations, through the use of a PO-Log – a partially ordered log of operations – inside the datatype. A semantically-based PO-Log compaction framework, using both causality and what we denote by causal stability, allows obtaining very compact replica state for pure op-based CRDTs, while also benefiting from small message sizes.
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download
Contributor : Hal Ifip Connect in order to contact the contributor
Submitted on : Monday, March 14, 2016 - 10:51:31 AM
Last modification on : Monday, December 13, 2021 - 4:02:02 PM
Long-term archiving on: : Sunday, November 13, 2016 - 5:20:11 PM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License



Carlos Baquero, Paulo Sérgio Almeida, Ali Shoker. Making Operation-Based CRDTs Operation-Based. 4th International Conference on Distributed Applications and Interoperable Systems (DAIS), Jun 2014, Berlin, Germany. pp.126-140, ⟨10.1007/978-3-662-43352-2_11⟩. ⟨hal-01287738⟩



Record views


Files downloads