Please use this identifier to cite or link to this item: http://repositorio.inesctec.pt/handle/123456789/4206
Title: Making Operation-Based CRDTs Operation-Based
Authors: Carlos Baquero
Paulo Sérgio Almeida
Ali Shoker
Issue Date: 2014
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 semanticallybased 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.
URI: http://repositorio.inesctec.pt/handle/123456789/4206
http://dx.doi.org/10.1007/978-3-662-43352-2_11
metadata.dc.type: conferenceObject
Publication
Appears in Collections:HASLab - Articles in International Conferences

Files in This Item:
File Description SizeFormat 
P-009-DMK.pdf264.55 kBAdobe PDFThumbnail
View/Open


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