PAPERS-15-007 · Paper — CRDTs — Conflict-free Replicated Data Types

The paper

The 2011 PODC paper “CRDTs — Conflict-free Replicated Data Types” by Marc Shapiro, Nuno Preguiça, Carlos Baquero and Marek Zawirski introduced a new way to keep replicated data consistent without coordination, and it quickly became a landmark in distributed systems.

Before this paper

Before this work, keeping replicas consistent required heavy coordination such as locking or consensus, which made systems slow and unavailable during network partitions. Skipping coordination meant updates could conflict, leading to painful manual reconciliation. The field lacked a principled way to get both high availability and correct convergence. As a result, many systems either sacrificed availability or endured complex conflict‑resolution logic.

The key idea

The key insight is that you can design data structures whose concurrent updates automatically merge correctly, no matter the order or timing, and without any coordination. These Conflict‑free Replicated Data Types guarantee that every replica will eventually converge to the same state. The paper shows that this property can be achieved mathematically, providing strong eventual consistency as a correctness condition.

How it works

State‑based CRDTs define a merge function that is commutative, associative, and idempotent; replicas periodically exchange their whole state and apply the merge, which always moves them toward a common state. Operation‑based CRDTs instead broadcast individual updates that are crafted to commute, so applying them in any order yields the same result. Both styles rely on the fact that the merge or the operations never lose information, ensuring convergence. The authors illustrate concrete designs such as counters, sets, and registers, each with specific merge rules or operation signatures. Replicas can run independently, periodically syncing their state or operations, and the mathematics guarantees they will agree eventually.

See it — merging without coordination

flowchart LR
  A["Replicas edit<br/>independently"] --> B["Operations designed<br/>to commute"]
  B --> C["Merge in any<br/>order"]
  C --> D["Same final state<br/>no conflicts"]

What they showed

The authors demonstrated that CRDTs enable highly‑available, partition‑tolerant replication that still converges correctly, without the cost of running consensus on every update.

What it changed

This work became the foundation for modern collaborative editing tools, offline‑first applications, and distributed caches like Redis’s conflict‑free types and Riak. By providing a clean, provable alternative to coordination‑heavy replication, it reshaped how engineers build resilient, low‑latency services. The paper’s designs are now standard building blocks in many real‑time systems. Next: Amazon Aurora.

The one-line takeaway

CRDTs let you get strong consistency without coordination, turning availability into a first‑class feature.

Read it / meet it

Reading the original paper gives you a clear view of the theory and concrete examples that still power today’s collaborative editors and sync services. You’ll see the ideas you encounter in tools like Google Docs, Notion, or offline‑first mobile apps, all built on the legacy of CRDTs.