CRDTs

Why two correct local writes can conflict

Suppose two replicas hold a counter with value 3. They disconnect, and each user increments the counter. If both replicas store the result as a plain assignment to 4, merging those assignments loses one increment. A CRDT counter records enough information to preserve both increments, so the merged value becomes 5.

Conflict-free replicated data types define what concurrent updates mean and how replicas converge. A replica can accept an update without coordinating with the others. Once two replicas have received the same set of updates, they deterministically reach the same state.

Temporary disagreement is still possible. A replica cannot show a remote update that has not reached it.

Wrong "Conflict-free means replicas never disagree."

Right Replicas may diverge while updates are in transit. The CRDT supplies deterministic convergence after they process the same updates.

Counters and sets encode specific rules

A grow-only counter keeps one count per replica. A replica increments its own component. Merge takes the maximum component for each replica, and the visible value is their sum.

type GCounter = Record<string, number>;

function merge(a: GCounter, b: GCounter): GCounter {
  const ids = new Set([...Object.keys(a), ...Object.keys(b)]);
  return Object.fromEntries(
    [...ids].map((id) => [id, Math.max(a[id] ?? 0, b[id] ?? 0)]),
  );
}

function value(counter: GCounter): number {
  return Object.values(counter).reduce((sum, n) => sum + n, 0);
}

A grow-only set merges with set union. A set that supports removal needs a concurrency rule. In an add-wins set, an add concurrent with a remove leaves the element present. A remove can only remove an addition it has observed. Remove-wins and last-writer-wins sets make different choices.

Wrong "CRDT means there is one universal, correct way to resolve a conflict."

Right Each CRDT specifies concurrency semantics for its operations. The application must choose semantics that match the product.

Collaborative text needs a sequence CRDT

Text is an ordered sequence, so concurrent insertion needs more than set union. Automerge uses a sequence CRDT for lists and collaborative text. Concurrent insertions and deletions are preserved, and replicas place concurrent insertions in the same order. Yjs likewise exposes shared CRDT-backed types for collaborative applications and can apply document updates in any order.

These libraries enable local edits and later synchronization. They do not remove the need for networking, persistence, permissions, or a product decision about what concurrent edits should mean.

State-based replication merges knowledge

A state-based CRDT, historically called a CvRDT, sends replica state to another replica and merges the two states. Its states form a join-semilattice. Every local update is an inflation in that partial order, and merge computes the join, or least upper bound.

The join has three properties that matter during synchronization:

• Commutative: receiving A then B has the same result as B then A.
• Associative: grouping a series of merges does not change the result.
• Idempotent: merging the same state again does not change the result.

Duplication and reordering are therefore safe for the merge itself. Updates still need to propagate eventually if replicas are expected to converge.

The grow-only counter makes the partial order concrete. Each component can only increase, and component-wise maximum is the join. A positive-negative counter stores two grow-only counters, one for increments and one for decrements. Its value is the increment total minus the decrement total.

Wrong "A state-based CRDT chooses the newest complete replica snapshot."

Right It joins the information from both states. Replacing one state with the other would discard concurrent updates.

Operation-based replication has a delivery contract

An operation-based CRDT, historically called a CmRDT, separates an update into a generator and an effector. The generator runs at the origin replica and produces the effector that other replicas apply.

Operation-based replication requires reliable delivery to every replica. With causal delivery, concurrent effectors must commute. If the network may deliver effectors without respecting causal order, all effectors must commute.

Wrong "Commutative operations make message loss harmless."

Right Commutativity handles order. A permanently lost increment is still a missing increment, so the replicas have not processed the same updates.

State-based and operation-based describe synchronization, not user-visible semantics. An add-wins set can be implemented in either style. The name tells you how replicas exchange information, while add-wins tells you the result of a concurrent add and remove.

Full state, deltas, and operation logs

Sending full state can repeat data a peer already knows. Delta-state CRDTs propagate delta-mutators, then merge those deltas as states. A peer with no prior state must receive enough joined state or deltas to reconstruct the current state; implementations may fall back to a full-state transfer. Operation-based replication often sends smaller effectors, but the system must satisfy its delivery and ordering contract and may need an outbound log.

This is an engineering choice with workload-specific costs. State size, update rate, replica count, causality metadata, and recovery behavior all affect the result. The CRDT proof obligations do not choose a transport for you.

Collaborative editors add another layer. Automerge treats replacing a whole object as a conflicting property assignment, while list and text operations retain fine-grained change information. Its text API converts edits into splice operations that can merge with concurrent changes.

Convergence is a conditional guarantee

Strong eventual consistency combines convergence with eventual delivery. Convergence says replicas that processed the same updates have the same state, independent of processing order. Eventual delivery says an update processed by one non-failed replica eventually reaches every other non-failed replica.

The CRDT defines the first part through its state merge or commutative effectors. The surrounding system must provide dissemination and durability, plus any deduplication and ordering that the chosen replication model requires.

Wrong "If a type is a CRDT, the transport can lose updates forever and replicas still converge."

Right A CRDT cannot reconstruct an update that never arrives. Its convergence statement compares replicas after they have processed the same updates.

Reads also have weaker visibility than a consensus-backed linearizable register. A local read can omit accepted remote operations that have not propagated yet. CRDTs offer low-latency local updates precisely because an update does not wait for global coordination.

The algebra behind each replication family

For a state-based design, check all three obligations: states form a join-semilattice, local updates are inflations, and merge returns the join. Commutativity, associativity, and idempotence follow from the join and make repeated anti-entropy exchanges safe.

For an operation-based design, write down the network assumption before claiming convergence. Under causal delivery, effectors for concurrent operations must commute. Under arbitrary delivery order, all effectors must commute. Reliable delivery is required in both cases, with duplicate suppression when the delivery layer may redeliver an operation.

This distinction explains why state-based and operation-based implementations of the same abstract set can have different wire and storage costs while exposing the same add-wins behavior.

When CRDTs beat consensus

CRDTs fit operations that may be accepted locally and have a defined merge under concurrency. Counters, add-wins sets, and collaborative sequences are common examples. Avoiding synchronous coordination can improve availability and hide inter-replica latency from the update path.

Global decisions remain global. The CRDT survey gives an auction example: replicas can collect bids under causal consistency, but closing the auction and selecting one winner requires global agreement.

The broader test is the application invariant. Coordination-avoidance research states it this way: if two independent local commit decisions can merge into an invalid state, replicas must coordinate to prevent that execution. A counter that freely decrements does not by itself protect a non-negative balance invariant. Escrow-style bounded counters can divide decrement rights among replicas, but a replica that exhausts its rights must fail the decrement or coordinate to obtain more.

Wrong "A deterministic tie-breaker replaces consensus for any business rule."

Right A tie-breaker can make replicas choose the same value after receiving the same candidates. It cannot establish that every eligible candidate is known or that a one-time global decision has occurred.

Metadata and product semantics are part of the design

CRDT implementations often track causal predecessors, replica identities, operation identifiers, or tombstones. Version vectors used by common designs have one entry per replica, so that metadata grows linearly with replica count. This can limit storage, communication, and local-operation performance. Delta synchronization reduces repeated full-state transfer but adds its own metadata and protocol requirements.

There is no neutral conflict policy. Add-wins, remove-wins, last-writer-wins, and multi-value registers expose different outcomes. Automerge preserves concurrent list insertions and deletions, but concurrent writes to one property use a deterministic winner while retaining the other values in a conflicts object. Replicas that receive the same changes make the same choice. Product correctness still depends on choosing the right choice.