A comprehensive study of Convergent and Commutative Replicated Data Types

Abstract : Eventual consistency aims to ensure that replicas of some mutable shared object converge without foreground synchronisation. Previous approaches to eventual consistency are ad-hoc and error-prone. We study a principled approach: to base the design of shared data types on some simple formal conditions that are sufficient to guarantee eventual consistency. We call these types Convergent or Commutative Replicated Data Types (CRDTs). This paper formalises asynchronous object replication, either state based or operation based, and provides a sufficient condition appropriate for each case. It describes several useful CRDTs, including container data types supporting both \add and \remove operations with clean semantics, and more complex types such as graphs, montonic DAGs, and sequences. It discusses some properties needed to implement non-trivial CRDTs.
Document type :
Reports
[Research Report] RR-7506, Inria – Centre Paris-Rocquencourt. 2011, pp.50


https://hal.inria.fr/inria-00555588
Contributor : Marc Shapiro <>
Submitted on : Thursday, January 13, 2011 - 7:34:51 PM
Last modification on : Wednesday, July 29, 2015 - 1:23:10 AM

File

techreport.pdf
fileSource_public_author

Identifiers

  • HAL Id : inria-00555588, version 1

Collections

Citation

Marc Shapiro, Nuno Preguiça, Carlos Baquero, Marek Zawirski. A comprehensive study of Convergent and Commutative Replicated Data Types. [Research Report] RR-7506, Inria – Centre Paris-Rocquencourt. 2011, pp.50. <inria-00555588>

Export

Share

Metrics

Consultation de
la notice

3506

Téléchargement du document

19344