CRDTs Explained

Definition

CRDTs are data structures designed so concurrent updates merge deterministically without coordination.

Why CRDTs Work (The Real Reason)

CRDTs work because they enforce algebraic guarantees. There is no distributed systems magic hiding in the merge path.

CRDTs are not a replication strategy. They are a mathematical constraint system on state transitions.

Three properties do the heavy lifting: commutativity, associativity, and idempotence.

• Commutativity handles network reordering. If updates arrive in a different order, the merged result is still the same.
• Associativity handles concurrent updates from many replicas. You can group and merge partial states in any merge tree and still converge.
• Idempotence handles duplication and retries. Applying the same update twice does not change the final value.

Most state-based CRDTs are modeled as semilattices. State is only allowed to move "forward" in the lattice partial order, not necessarily upward in wall-clock time or numeric value. Merge computes the least upper bound of two states, which is what makes convergence deterministic.

Key Concepts

• Commutative/associative/idempotent merge rules.
• State-based and operation-based CRDT variants.
• Eliminates many write-write conflict classes.
• Trades storage/metadata for merge safety.

The Three Models of CRDTs

State-Based CRDTs (CvRDT)

State-based CRDTs replicate full state between nodes and merge by join. They are simple and robust in unreliable networks because duplicate deliveries are safe by design. The tradeoff is bandwidth, especially for large objects with high write rates.

Operation-Based CRDTs (CmRDT)

Operation-based CRDTs ship operations instead of full state. This reduces payload size but requires delivery guarantees that preserve the assumptions of the data type, typically causal delivery in the sync layer. The tradeoff is protocol complexity: the network contract matters more because correctness depends on more than merge alone.

Delta CRDTs (Modern Approach)

Delta CRDTs send only changes, not full snapshots, while preserving join-based convergence behavior. Delta-CRDTs are to CRDTs what write-ahead logs are to databases.

How It Works

Replicas apply local updates and exchange either full state or operations; merge logic guarantees convergence regardless of message order.

In production, this usually sits inside broader eventual consistency tradeoffs, and it depends on careful transport design for retries, redelivery, and batching.

CRDTs are one approach to eventual consistency, but unlike retry-driven reconciliation or queue-driven coordination, they push more of the correctness burden into the data model itself.

Worked Example: PN-Counter

A PN-Counter is a good example of how CRDTs preserve merge safety without central coordination. Instead of storing one mutable number, it stores two grow-only counters: one for increments and one for decrements.

Replica A increments by 5
Replica B increments by 3

Positive component:
A: 5
B: 3

Negative component:
A: 0
B: 0

Merged value = (5 + 3) - (0 + 0) = 8

The key idea is that each component only moves forward. Merge takes the per-replica maximum for each component, so reordering, duplication, and partial delivery do not break convergence.

CRDT Design Patterns

Monotonic Structures

G-Counter and G-Set only grow. Because state moves in one direction, convergence is straightforward and operationally predictable.

Reversible Structures

PN-Counter and OR-Set use decomposition patterns to represent "undo" behavior without violating monotonic merge rules. A PN-Counter splits increments and decrements into separate grow-only components. OR-Set tracks add/remove intent with identity metadata.

Conflict-Resolving Registers

LWW Register resolves by timestamp wins, which is compact but can drop concurrent intent. Multi-Value Register preserves concurrency by retaining multiple values until later application-level resolution.

Ordered Structures (Hard Mode)

RGA, Logoot, and LSEQ handle ordered insertion under concurrency with stable identifiers, ordering metadata, and tombstone-like bookkeeping.

The hard part is that concurrent edits break the idea of a simple array index. Ordered CRDTs solve identity under concurrency, not fixed position in a mutable list.

Sets are easy. Lists are hard. Ordered CRDTs are where theory meets pain.

CRDTs vs Consensus Systems

CRDTs embrace conflicts and resolve them. Consensus systems prevent conflicts entirely.

Where CRDTs Are Used

CRDTs show up where multi-region writes and disconnected clients are normal. This includes systems inspired by Riak, Redis CRDT replication patterns, collaborative editors, and offline-first mobile apps.

The common requirement is safe merge under weak connectivity: edge sync, intermittent mobile networks, and active/active region topologies.

CRDT Architecture Pattern

Client (offline capable)
        ↓
Local CRDT replica
        ↓
Sync layer (anti-entropy / gossip / pubsub)
        ↓
Merge function (deterministic)
        ↓
Eventually consistent global state

CRDTs shift complexity from coordination to data modeling.

Production Implications

CRDTs reduce human conflict resolution burden in distributed collaboration systems. In practice, some teams on Dynamo-style or Cassandra-style architectures also adopt CRDT-like application-level structures for counters, sets, and presence state where deterministic merge behavior matters.

Your transport and recovery design still matters: retry and idempotency discipline prevents accidental semantics drift, and backpressure and system stability controls keep sync floods from becoming outages.

For write-heavy pipelines, pair CRDT merge behavior with queueing discipline and admission control from queue design under load.

When CRDTs Are the Wrong Tool

CRDTs guarantee convergence—not correctness.

Financial systems

Ledgers and payment workflows usually require strict ordering and transactional guarantees that CRDT merge semantics do not provide on their own.

Global constraints

Hard uniqueness requirements and inventory limits require coordination or escrow-like mechanisms across replicas.

For example, inventory is not just a merge problem. If two replicas both believe one item is available and both sell it concurrently, convergence alone does not preserve the business invariant that stock cannot go below zero.

Cross-object invariants

CRDTs cannot guarantee correctness for invariants that span multiple objects or bounded resources without additional coordination protocols.

When to Use / Not Use

Use It When

• Counters, sets, presence, and collaboration artifacts.
• Offline-first synchronization flows.

Avoid It When

• Domains requiring strict global invariants and serializable transactions.
• Extremely constrained payload footprints where metadata is too costly.

Mental Models for CRDTs

• "Append-only history disguised as state"
• "Every write must be replayable in any order"
• "State is a monotonic lattice, not a mutable value"

CRDTs are one of the few approaches in distributed systems that completely eliminate coordination from the write path. Instead of asking "who wins," they redefine the problem so that all writes can win simultaneously—and still converge.

If you want the implementation mindset behind these ideas, read Designing a CRDT from Scratch.

Related Reading

• Designing a CRDT from Scratch
• What Is Eventual Consistency? (pillar guide)
• Vector Clocks vs Timestamps
• Anti-Entropy, Gossip, and Read Repair

Key Takeaways

• CRDTs eliminate coordination in the write path.
• They rely on algebraic guarantees.
• They trade correctness constraints for availability.
• They are ideal for offline-first and geo-distributed systems.