Blog by Simon Frey

Conflict-free replicated data types to archive eventual consistency

1 min read

Hola persona grandiosa,

after last weeks topic on the CAP theorem, this week is a lot more practical. A conflict-free replicated data type (CRDT) helps you build a distributed system where all nodes converge to the same state. I challenge you to read the paper and build a minimal distributed system with a CRDT. Feel free to share your results in the Telegram group, we are happy to learn what you learned.


Abstract:

Replicating data under Eventual Consistency (EC) allows any replica to accept updates without remote synchronization. This ensures performance and scalability in large-scale distributed systems (e.g., clouds). However, published EC approaches are ad-hoc and error-prone. Under a formal Strong Eventual Consistency (SEC) model, we study sufficient conditions for convergence. A data type that satisfies these conditions is called a Conflict-free Replicated Data Type (CRDT). Replicas of any CRDT are guaranteed to converge in a self stabilising manner, despite any number of failures. This paper formalizes two popular approaches (state- and operation-based) and their relevant sufficient conditions. We study a number of useful CRDTs, such as sets with clean semantics, supporting both add and remove operations, and consider in depth the more complex Graph data type. CRDT types can be composed to develop large-scale distributed applications, and have interesting theoretical properties.

Download Link:

https://hal.inria.fr/inria-00609399/document


Our little paper community is at 342 subscribers. Help to bring it up to 500 by sharing the newsletter with your friends, colleagues, kids and grandparents.

simon-frey.com/weeklycspaper

If you have any paper recommendation for me, please do not hesitate to approach me via [email protected] (Please keep the Backend & DevOps topic focus in mind)


With much love,

Simon Frey

Back to top