%0 Conference Proceedings
%T Making Operation-Based CRDTs Operation-Based
%+ High-Assurance Software Laboratory [Braga, Portugal] ( HASLab )
%A Baquero, Carlos
%A Almeida, Paulo, Sérgio
%A Shoker, Ali
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 4th International Conference on Distributed Applications and Interoperable Systems (DAIS)
%C Berlin, Germany
%Y David Hutchison
%Y Takeo Kanade
%Y Bernhard Steffen
%Y Demetri Terzopoulos
%Y Doug Tygar
%Y Gerhard Weikum
%Y Kostas Magoutis
%Y Peter Pietzuch
%Y Josef Kittler
%Y Jon M. Kleinberg
%Y Alfred Kobsa
%Y Friedemann Mattern
%Y John C. Mitchell
%Y Moni Naor
%Y Oscar Nierstrasz
%Y C. Pandu Rangan
%I Springer
%3 Distributed Applications and Interoperable Systems
%V LNCS-8460
%P 126-140
%8 2014-06-03
%D 2014
%R 10.1007/978-3-662-43352-2_11
%Z Computer Science [cs]
%Z Computer Science [cs]/Networking and Internet Architecture [cs.NI]Conference papers
%X 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.
%G English
%Z TC 6
%Z WG 6.1
%2 https://inria.hal.science/hal-01287738/document
%2 https://inria.hal.science/hal-01287738/file/326177_1_En_11_Chapter.pdf
%L hal-01287738
%U https://inria.hal.science/hal-01287738
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-WG
%~ IFIP-LNCS-8460
%~ IFIP-TC6
%~ IFIP-WG6-1