Past Meetup

CRDT: Conflict-free replicated data types

This Meetup is past

92 people went

Concur Technologies, 3rd Floor, B-block, Bagmane Laurel

Bagmane Tech Park, Bysandra, C V Raman Nagar · Bangalore

How to find us

Google Maps has accurate location of Concur. Call Vipin: 9740870100, Shantanu: 9972869200 or Jaseem: 9901644408 if you have difficulty finding the place.

Location image of event venue

Details

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