Oct 2011 | Marc Shapiro, Nuno Preguiça, Carlos Baquero, Marek Zawirski
Conflict-free Replicated Data Types (CRDTs) are data types that ensure eventual consistency in distributed systems without requiring coordination or synchronization. This paper introduces a formal model of Strong Eventual Consistency (SEC), which guarantees that replicas converge to a correct state despite failures. CRDTs are defined by two sufficient conditions: monotonicity in a semilattice and commutativity of operations. The paper presents several CRDTs, including sets, counters, and graphs, and shows how they can be composed to build large-scale distributed applications. It also demonstrates that SEC is incomparable to sequential consistency and that CRDTs can be implemented in both state-based and operation-based styles. The paper concludes that CRDTs provide a clean and efficient solution for eventual consistency in distributed systems, and that further research is needed to fully understand their theoretical and practical implications.Conflict-free Replicated Data Types (CRDTs) are data types that ensure eventual consistency in distributed systems without requiring coordination or synchronization. This paper introduces a formal model of Strong Eventual Consistency (SEC), which guarantees that replicas converge to a correct state despite failures. CRDTs are defined by two sufficient conditions: monotonicity in a semilattice and commutativity of operations. The paper presents several CRDTs, including sets, counters, and graphs, and shows how they can be composed to build large-scale distributed applications. It also demonstrates that SEC is incomparable to sequential consistency and that CRDTs can be implemented in both state-based and operation-based styles. The paper concludes that CRDTs provide a clean and efficient solution for eventual consistency in distributed systems, and that further research is needed to fully understand their theoretical and practical implications.