Papers /

Shapiro-INRIA-2011

Reading

Cycling

Mountaineering

X-Wing

Infinity

Warhammer 40k

Hobby

Nook

sidebar

Shapiro-INRIA-2011

A Comprehensive Study of Convergent and Commutative Replicated Data Types

Shapiro, Preguica, Baquero, Zawirski

eventual consistency crdt convergence asynchronous replication

@techreport{shapiro:inria-2011,
  title={A Comprehensive Study of Convergent and
         Commutative Replicated Data Types},
  author={Shapiro, Marc and Pregui{\c{c}}a, Nuno and
          Baquero, Carlos and Zawirski, Marek},
  year={2011},
  month={January},
  institution={Institut National de Recherche
               en Informatique et en Automatique ({INRIA})},
  number={7506},
  note={\url{https://hal.inria.fr/file/index/docid/555588/filename/techreport.pdf}}
}

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.

Local Copy: PDF

Recent Changes (All) | Edit SideBar Page last modified on May 07, 2015, at 09:53 AM Edit Page | Page History
Powered by PmWiki