Course contentsShow
← Computer Science
Lesson 2703 of 2,87260. Distributed Data and CommunicationFree lesson

Conflict-Free Replicated Data Types (CRDTs)

Designing data structures that guarantee convergence without coordination by ensuring commutative and idempotent operations.

Conflict-Free Replicated Data Types (CRDTs)

What you'll learn: How to design data structures that automatically merge concurrent updates without coordination, guaranteeing eventual consistency.

The Core Idea

Imagine multiple people editing a shared shopping list offline. When they sync, how do you merge their changes without conflicts? CRDTs solve this by designing data structures where the order of operations doesn't matter and applying the same operation multiple times produces the same result.

CRDTs guarantee convergence — all replicas eventually reach the same state — by ensuring operations are:

  • Commutative: A ⊕ B = B ⊕ A (order doesn't matter)
  • Idempotent: A ⊕ A = A (duplicates don't change the outcome)

Why This Matters

In distributed systems with eventual consistency, you saw how conflicts arise. Last-Write-Wins discards data, and vector clocks only detect conflicts. CRDTs go further: they prevent conflicts through mathematical properties.

Two Flavors

State-based CRDTs (CvRDTs): Replicas exchange entire states and merge them using a commutative, associative, idempotent merge function. Think: each replica sends its full shopping list, and merging combines all items.

Operation-based CRDTs (CmRDTs): Replicas broadcast operations that commute. The operations themselves must be designed to work in any order. Think: "add milk" and "add bread" can happen in either sequence.

Simple Example

A Grow-Only Set (G-Set) allows only additions. Since adding the same item twice doesn't change the set (idempotent) and adding items in different orders produces the same set (commutative), convergence is guaranteed.

Key Takeaway: CRDTs use mathematical properties (commutativity and idempotence) to design data structures that automatically merge without coordination, enabling true conflict-free eventual consistency.