CRDT: Conflict-free 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).

Reference Paper: A comprehensive study of Convergent and Commutative Replicated Data Types (http://hal.upmc.fr/inria-00555588/document)

Overview: Replication is a fundamental concept of distributed systems. Any data update must be replicated to all peers in the system, if the system were to behave like a single system. This is usually achieved by introducing coordination, but it is expensive and can become infeasible quickly. An alternative approach is to build systems that are eventually consistent by removing coordination from the hot path, but there can be conflicts and conflict resolution is generally complex.

CRDT's are any data structures (and associated operations) that have some simple mathematical properties. These properties are immensely useful in building distributed systems that are eventually consistent and conflict free by design. There are may known CRDT's and the paper listed above catalogs them. While CRDT's are not general purpose, a lot of real life problems can be solved by using CRDT's.

In this talk, I hope to cover everything needed from the ground up, including the rudimentary mathematics needed to understand CRDT's, walk through some of the data structures and prove that they are CRDT's, discuss problems that can be solved with CRDT's, their practical limitations, along with a general discussion/rant on distributed systems, consensus and consistency models.

• Vipin