Conflict-free Replicated Data Types

Nuno Manuel Ribeiro Preguiça

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

318 Citations (Scopus)

Abstract

Replicating data under Eventual Consistency (EC) allows any replica to accept updates without remote synchronisation. This en- sures 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 suf- ficient conditions for convergence. A data type that satisfies these con- ditions 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 formalises two popular ap- proaches (state- and operation-based) and their relevant sufficient con- ditions. 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 the- oretical properties.
Original languageUnknown
Title of host publicationLecture Notes in Computer Science
Pages386-400
DOIs
Publication statusPublished - 1 Jan 2011
EventStabilization, Safety, and Security of Distributed Systems (2011) -
Duration: 1 Jan 2011 → …

Conference

ConferenceStabilization, Safety, and Security of Distributed Systems (2011)
Period1/01/11 → …

Cite this