Authors
Marc Shapiro, Nuno Preguiça, Carlos Baquero, Marek Zawirski, P Fatourou
Publication date
2011/1/7
Journal
Bulletin of the EATCS
Issue
104
Pages
67-88
Description
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 and monotonic DAGs. It discusses some properties needed to implement non-trivial CRDTs.
Total citations
20122013201420152016201720182019202020212022202320246812911971027452
Scholar articles
M Shapiro, N Preguiça, C Baquero, M Zawirski - Bulletin of EATCS, 2013
N Preguiça, C Baquero, M Zawirski, M Shapiro - 2011