Consistency without concurrency control, in Cloud and P2P systems

The ConcoRDanT project in brief

The ConcoRDanT is a collaborative research project, funded by French National Agency for Research (ANR), program ANR Blanc from 2010 to 2014. Its aim is to investigate Commutative Replicated Data Types (CRDTs). CRDTs are unique in that they encapsulate concurrency and distribution, and that they guarantee (eventual) consistency by construction, thanks to some simple mathematical properties. CRDTs support fast, local updates without requiring synchronisation. They scale to large-scale distributed systems, such as P2P and Cloud systems. They require no complex concurrency control and no rollback, and to large-scale distributed systems, such as P2P and Cloud systems.

The partners in the project are:

• INRIA (Regal team).
• LORIA (SCORE team).

• U. de Nantes (GDD team).
• U. Nova de Lisboa (CITI institute).

The project coordinator is Marc Shapiro from INRIA.

Introduction to the project

Massive computing systems and their applications suffer from a fundamental tension between scalability and data consistency. Avoiding the synchronisation bottleneck requires highly skilled programmers, makes applications complex and brittle, and is error-prone.

The ConcoRDanT project investigates a promising new approach that is simple, scales indefinitely, and provably ensures eventual consistency. A Commutative Replicated Data Type (CRDT) is a data type where all concurrent operations commute. If all replicas execute all operations, they converge; no complex concurrency control is required. We have shown in the past that CRDTs can replace existing techniques in a number of tasks where distributed users can update concurrently, such as co-operative editing, wikis, and version control. However CRDTs are not a universal solution and raise their own issues (e.g., growth of meta-data).

The ConcoRDanT project engages in a systematic and principled study of CRDTs, to discover their power and limitations, both theoretical and practical. Its outcome will be a body of knowledge about CRDTs and a library of CRDT designs, and applications using them. We are hopeful that significant distributed applications can be designed using CRDTs, a radical simplification of software, elegantly reconciling scalability and consistency.

Further information

For further information, please see the project proposal. The project reference number is ANR-10-BLAN 0208.