CRDT

A conflict-free replicated data type (CRDT) is a data structure designed for distributed systems that guarantees eventual consistency without requiring coordination between replicas. The key insight is that if the update operations on a data structure satisfy certain algebraic properties — commutativity, associativity, and idempotence — then replicas can apply updates in any order and still converge to the same final state. CRDTs were formalized by Marc Shapiro et al. in 2011 and have become the foundation of collaborative editing, distributed databases, and edge computing. The commutativity requirement is the critical constraint: it means that updates must form an Abelian structure under merge, which is why CRDTs cannot represent all data types. They work for counters, sets, and graphs with specific merge semantics, but they fail for data structures where order matters — like sequences with positional insertions. The CRDT framework is therefore a boundary marker: it identifies the class of distributed computations that can proceed without consensus, and it demonstrates that this class is precisely the class of Abelian operations. The boundary between CRDT-applicable and CRDT-inapplicable problems is the boundary between distributed systems that can scale linearly and distributed systems that require global coordination.