Every developer building a real-time collaborative tool or an offline-first app eventually runs into the sync wall.

The traditional solution for collaborative editing was Operational Transformation (OT), the engine behind Google Docs. But OT has a strict operational constraint: it requires a central server to establish an authoritative timeline and rewrite concurrent operations against each other. If two mobile devices want to edit a document peer-to-peer over local Wi-Fi, or if a user goes into an airplane cabin for four hours, OT falls apart without a central coordinator to arbitrate ordering.

Conflict-free Replicated Data Types (CRDTs) take a completely different mathematical route. Instead of maintaining an ordering queue on a central server, CRDTs structure data using abstract algebra so that distributed replicas can accept concurrent edits in isolation and merge them in any order without locks, round-trips, or human intervention.

Here is what is actually happening underneath the hood of libraries like Automerge, Yjs, and modern local-first databases.

The Math: Why Join-Semilattices Guarantee Convergence

In standard distributed databases, reaching agreement requires consensus algorithms like Paxos or Raft. Replicas elect a leader, serialize writes via a log, and block until a quorum acknowledges the entry.

CRDTs achieve Strong Eventual Consistency (SEC) without leader election or two-phase commits. The formal definition of SEC states: any two replicas that have received the same set of updates will be in the identical state, regardless of the order in which updates arrived.

This guarantee rests on a mathematical structure called a bounded join-semilattice.

A semilattice is a partially ordered set $(S, \le)$ equipped with a binary operation called the join (denoted as $\sqcup$, or least upper bound). For a data structure to qualify as a state-based CRDT (CvRDT), its merge function must satisfy three algebraic properties:

  1. Commutative: $x \sqcup y = y \sqcup x$. The order in which replica A and replica B exchange updates does not matter.
  2. Associative: $(x \sqcup y) \sqcup z = x \sqcup (y \sqcup z)$. Batching updates or merging them across intermediate hops yields the exact same state.
  3. Idempotent: $x \sqcup x = x$. Receiving duplicate network packets or re-running a synchronization step has zero side effects.

Furthermore, updates must be inflationary: every local state change must move monotonically forward in the partial order ($s \le s \sqcup u$). Because state only moves upward in the lattice, replicas cannot diverge into unmergeable branches. When two nodes exchange states, taking the join produces the unique least upper bound that subsumes both states.

 [State A ⊔ State B] <-- Least Upper Bound (Merged State) / \ / \ [State A] [State B] \ / \ / [Initial State]

CvRDT vs CmRDT: State vs Operation Replication

There are two classical ways to implement a CRDT, though modern systems frequently blend them.

+------------------+-----------------------------+-----------------------------+ | Dimension | State-based (CvRDT) | Operation-based (CmRDT) | +------------------+-----------------------------+-----------------------------+ | What is sent | Full replica state (or diff)| Small mutation operations | | Network layer | Best-effort (unreliable OK) | Causal broadcast required | | Delivery order | Arbitrary (packet reorder OK)| Must preserve causality | | Idempotency | Built-in (x ⊔ x = x) | Must be handled by receiver | | Bandwidth cost | Grows with total state size | Small per-operation payloads| +------------------+-----------------------------+-----------------------------+

1. Convergent Replicated Data Types (CvRDT)

In a pure state-based CRDT, local mutations alter only the local replica. To synchronize, replica A serializes its entire internal state and transmits it over the network to replica B. Replica B executes merge(stateA, stateB) to compute the join.

Because the join operation is commutative, associative, and idempotent, the transport layer can drop packets, duplicate packets, or reorder packets without corrupting state. The obvious failure mode is bandwidth: as your document grows to megabytes, transmitting the full state on every keystroke becomes unusable.

2. Commutative Replicated Data Types (CmRDT)

Operation-based CRDTs separate mutation into two phases: a local generator and a remote effector. When you type a character, the generator inspects local state and emits a compact operation packet (for example: Insert(char='x', id=12, after=11)). This operation is broadcast to all peers.

CmRDTs save massive bandwidth because payloads are tiny. However, they shift the burden to the transport layer. The communication channel must guarantee causal-order delivery (usually enforced using vector clocks) and ensure that non-idempotent operations are never delivered twice.

3. The Modern Solution: Delta-State CRDTs

To get the network robustness of CvRDTs without the bandwidth penalty, libraries rely on delta-state CRDTs. Instead of shipping the entire state or assuming a flawless causal network, nodes transmit "deltas" (state changes accumulated since the last known synchronization boundary). Because the delta is itself an element of the join-semilattice, it merges using the exact same idempotent join operation.

Building Blocks in Code: Counters and LWW Registers

To see the math in action, look at how basic primitive types work.

The Grow-Only Counter (G-Counter)

A simple integer counter cannot be merged with max(a, b) if both nodes incremented concurrently, nor can it be merged with a + b without double-counting past increments.

The solution is an array where each node updates only its own assigned slot. The merge function takes the element-wise maximum across all nodes:

class GCounter: def __init__(self, node_id: str): self.node_id = node_id self.state: dict[str, int] = {} def inc(self, value: int = 1) -> None: self.state[self.node_id] = self.state.get(self.node_id, 0) + value def value(self) -> int: return sum(self.state.values()) def merge(self, remote: "GCounter") -> None: all_keys = set(self.state.keys()) | set(remote.state.keys()) for k in all_keys: self.state[k] = max(self.state.get(k, 0), remote.state.get(k, 0))

To support decrements, you compose two G-Counters into a PN-Counter (Positive-Negative Counter), where the total value is P.value() - N.value().

The Last-Writer-Wins Register (LWW-Register)

For scalar fields like a user profile name, you cannot easily combine strings mathematically. Systems fall back to an LWW-Register, storing (value, timestamp, client_id):

import time class LWWRegister: def __init__(self, client_id: str, value: str = ""): self.client_id = client_id self.value = value self.timestamp = time.time_ns() def set(self, new_value: str) -> None: self.value = new_value self.timestamp = time.time_ns() def merge(self, remote: "LWWRegister") -> None: # Tie-breaker using client_id if timestamps match exactly if (remote.timestamp, remote.client_id) > (self.timestamp, self.client_id): self.value = remote.value self.timestamp = remote.timestamp self.client_id = remote.client_id

Notice the catch: physical wall-clock timestamps drift across devices. If a client clock is skewed 10 minutes into the future, its updates will silently overwrite newer writes from synchronized peers until other clocks catch up.

The Hard Part: Sequence CRDTs and Text Editing

Counters and key-value maps are straightforward because keys are independent. Text editing is where CRDT implementations get complicated.

In a text document, characters are ordered relative to each other. If user A has "hello" and inserts "!" at index 5, while user B concurrently deletes 'h' at index 0, raw array indexes break immediately. If you apply user A's insert after user B's delete, the exclamation mark lands in the wrong spot because the string shifted left.

The Replicated Growable Array (RGA)

Production CRDTs like Automerge and Yjs treat text not as an array of characters, but as a directed graph or linked list of immutable character nodes.

Each character inserted receives a globally unique, immutable identifier:
$$\text{ID} = (\text{client_id}, \text{logical_clock})$$

When an item is inserted, it records the ID of the character immediately preceding it (origin or after_id):

[Start] <--- (Node 1: 'H', id=(A, 1), after=Start) <--- (Node 2: 'i', id=(A, 2), after=(A, 1))

If client A inserts 'a' after 'H', and client B concurrently inserts 'o' after 'H', both nodes point to (A, 1) as their anchor. When replicas merge, they need a deterministic tie-breaking rule to decide whether the text becomes "Hoa" or "Hao".

Algorithms like RGA and Yjs's YATA compare the unique IDs (e.g., higher logical clock or higher client UUID wins) to place the sibling nodes consistently on every machine.

The Tombstone Problem: Why Deleted Code Lives Forever

Here is the central engineering challenge of sequence CRDTs: you cannot simply free or delete a node from memory.

Imagine this sequence of events:

  1. Client A and Client B start with the word "CAT". Node 'A' has ID (1, 2).
  2. Client A deletes 'A', leaving "CT".
  3. Concurrently, Client B (offline) types 'R' immediately after 'A', intending to write "CART". Node 'R' has after_id = (1, 2).

If Client A physically removed 'A' from its local linked list upon deletion, what happens when Client B's update finally arrives over the network?

Client B sends: Insert 'R', after=(1, 2) Client A's document: Node (1, 2) does not exist!

Node 'R' has lost its parent anchor. Its geometric position in the document graph is undefined.

To prevent graph breakage, sequence CRDTs convert deleted characters into tombstones. The node remains in the linked list to preserve structural routing for concurrent edits, but its visible flag is set to deleted:

[Node 'C'] -> [Node 'A' (TOMBSTONE)] -> [Node 'T']

When rendering the document on screen, the traversal simply skips over tombstones. But in memory and on disk, every typo, backspace, and rewrite remains permanently preserved. In a document that has undergone months of continuous editing, 80% to 90% of the nodes in memory can be tombstones.

How Modern Systems Manage Tombstones

Because unbounded memory growth kills long-running processes, libraries use specific optimization strategies:

  1. Compound Run-Length Encoding: Instead of allocating one JavaScript object per character (which ballooned early CRDT prototypes to 40x memory overhead), modern Yjs and Automerge group consecutive keystrokes from the same user into a single continuous struct: Item { content: "hello world", length: 11, id_start: 100 }.
  2. Discarding Payloads with Lightweight GC: When a node is deleted, Yjs strips the actual character payload from memory and replaces it with a bare GC struct that retains only its length and ID sequence. The text string is reclaimed, leaving behind only the routing metadata.
  3. Consensus-Based Tombstone Purging: In peer-to-peer systems, you can safely remove a tombstone completely only when you can mathematically prove that every single peer in the network has observed the deletion and progressed past that point in causal time.

Proving that all peers have seen an edit requires a global state exchange (such as tracking the minimum vector clock across all known clients). If one offline peer disappears for three weeks, garbage collection must halt to preserve compatibility for that peer's eventual reconnect.

Where CRDTs Fail: The Limits of Commutative Math

CRDTs are powerful, but they are not universal drop-in replacements for relational databases or consensus engines. They fail when business logic depends on invariants that span multiple records:

  1. Unique Constraints: If Alice registers the username "alex" while offline on her laptop, and Bob registers "alex" while offline on his phone, a CRDT cannot resolve this cleanly. Neither write is invalid in isolation. To guarantee uniqueness without human intervention, you need a coordinator or a Paxos/Raft consensus group.
  2. Conservation of Balance: You cannot build an offline CRDT for a checking account where the balance must never drop below zero. If an account has $100, and two offline nodes concurrently withdraw $80, both operations are locally valid. When they sync, the merged balance would be -$60.
  3. Complex Foreign Key Cascades: In relational models, deleting an organization cascades to its members. If another client concurrently invites a new member into that organization, the eventual state can end up with orphaned references unless complex causal trees are maintained.

Summary Takeaway

CRDTs replace network locking with algebraic guarantees. By restricting merge functions to commutative, associative, and idempotent operations, replicas can run completely disconnected and reach identical states upon reconnection.

The cost is structural metadata: unique identifiers for every mutation, vector clocks to track causality, and tombstones that linger to anchor concurrent writes.

When your application needs high availability, instant local UI response, and painless offline collaboration, understanding this math lets you design state structures that converge naturally instead of fighting edge cases in manual conflict handlers.