A replicated value does not become conflict-free because every replica eventually exchanges messages. If two replicas overwrite one another with whole snapshots, delayed delivery can make them oscillate or preserve whichever message happened to arrive last. Convergence needs an algebra that makes duplication and reordering harmless, plus update rules that never discard information another replica may still need.
Conflict-free replicated data types, or CRDTs, encode that algebra in the data type. State-based CRDTs make replica states merge through a join operation. Operation-based CRDTs make concurrently deliverable effects commute under a stated broadcast contract. Neither family discovers user intent, enforces every business invariant, or turns partitions into transactions. It guarantees a narrower and highly useful property: replicas that have incorporated the same updates can compute equivalent state without choosing a single writer for every update.
The central thesis is: CRDT behavior should be derived from merge or operation laws before it is described as eventual consistency. The laws explain why replicas converge. Causal metadata explains which updates have been observed. Product semantics explain whether the converged answer is desirable. Keeping those layers separate prevents a deterministic merge from being mistaken for a correct domain decision.
Make Convergence a Checkable Claim
Strong eventual convergence can be stated without referring to a particular network delay: any two replicas that have incorporated the same set of updates are in equivalent states. Eventual delivery then gives eventual convergence when updates stop. Availability during a partition is a deployment property; convergence after exchange is a data-type property.
For a state-based CRDT, replicas may receive old states, duplicate states, or states in different orders. The merge function must make those schedules irrelevant. If merge(a, b) depends on which message arrived last, the data type has merely moved conflict resolution into an accident of transport.
For an operation-based CRDT, replicas exchange operations rather than complete states. The network contract is stronger: operations usually need reliable delivery, causal ordering where effectors rely on it, and exactly-once application or explicit duplicate suppression. Concurrent operations must commute because different replicas may observe them in either order. If operations do not commute and the protocol supplies no common order, replicas can diverge.
State transfer tolerates duplication and reordering but can be large. Operation transfer can be compact, but delivery and recovery become part of correctness. Delta-state CRDTs send joinable fragments to reduce bandwidth while retaining state-based laws. None of these choices provides linearizability: replicas may answer before seeing remote updates, so products still need visibility and reconciliation expectations.
Derive State-Based CRDTs from a Join
Let replica states form a partially ordered set . The order means “contains no more information than.” For any two states and , define a least upper bound, or join, : a state containing the information in both, with no unnecessary greater state under the order.
The join obeys three laws:
Commutativity makes arrival order irrelevant. Associativity makes batching and merge-tree shape irrelevant. Idempotence makes duplicate delivery harmless. Together they let anti-entropy exchange arbitrary snapshots without coordinating a single global sequence.
Local updates must be inflationary:
An update moves upward in the information order. It may represent logical removal, but it cannot simply erase causal evidence that an old replica could later resend. That is why many state-based CRDTs retain tombstones or causal contexts: the representation grows even when the abstract value shrinks.
These definitions form a join-semilattice and provide the convergence proof. Specify the state, partial order, join, mutators, and query, then prove the join laws and inflation over reachable states. The query itself need not be monotone: a set can hide a removed element while internal state grows by retaining the addition and its removal evidence. That evidence prevents an old replica from resurrecting the element.
Work Through a Grow-Only Counter
A grow-only counter, or G-Counter, is the smallest useful derivation. Each replica owns one component in a map from stable replica ID to a nonnegative integer. Replica A increments only component A. The query sums all components.
Define the partial order componentwise: when every component in is less than or equal to the same component in , treating a missing component as zero. Define join as componentwise maximum:
Maximum is associative, commutative, and idempotent. Incrementing the local component is inflationary. Therefore arbitrary snapshot duplication and reordering cannot lose an acknowledged increment already represented by one of the merged states.
Start A and B at {A: 0, B: 0}. During a partition, A increments twice and reaches {A: 2, B: 0}. B increments three times and reaches {A: 0, B: 3}. Merging either direction yields {A: 2, B: 3}, whose query is 5. Delivering A’s old {A: 1, B: 0} afterward changes nothing because componentwise maximum retains 2 and 3. Delivering the merged state twice also changes nothing.
Addition of snapshots would be wrong. Merging {A: 2} twice by addition would count A’s increments twice, violating idempotence. The counter accumulates locally by increment, but replicas reconcile by maximum because each component is one replica’s cumulative knowledge.
Replica identity is part of the proof. If A restarts at zero with the same ID, peers holding A: 2 ignore its new increments. Persist the component or assign a fresh incarnation after uncertain recovery; retire identities only when old state cannot return. A positive-negative counter joins separate increment and decrement G-Counters, but concurrent decrements can still violate a global nonnegative bound. Convergence and invariant preservation are separate claims.
Derive Removal with an Observed-Remove Set
Removal exposes why causal evidence matters. A simple grow-only set can union additions but cannot remove. An observed-remove set gives every addition a globally unique tag, often called a dot. Internal state contains a grow-only set of tagged additions and a grow-only set of removed tags .
To add element x, create a never-reused tag d and add (x, d) to . To remove x, add to every tag for x currently observed in . The query includes x when at least one tagged addition for x is not in . Merge unions both sets:
Set union satisfies the join laws, and both mutators only add internal information. The semantics are “remove what I observed.” A concurrent addition with a tag unknown to the remover survives, producing add-wins behavior.
Consider a replicated set of reviewers. East adds Ana with tag e1 and synchronizes that state to West. A partition begins. East removes Ana, so its removal set becomes {e1}. Concurrently, West receives a new request to add Ana and creates tag w1. Before merge, East’s abstract set excludes Ana; West’s includes her.
After merge, additions are {(Ana,e1), (Ana,w1)} and removals are {e1}. Tag w1 remains live, so Ana is present. East’s remove cannot erase an addition it never observed. If West had made no concurrent add, the merged state would contain only tag e1, which is removed, and Ana would be absent. If Ana is later re-added, a fresh tag such as e2 survives the old tombstone.
The deterministic outcome is still a product choice. Baskets may prefer add-wins, bans may require remove-wins, and security revocation may require coordination. “Conflict-free” means replicas apply the same rule, not that the rule captures every intent.
This representation retains additions and tombstones until causal stability proves that no replica or delayed message can reintroduce an addition without its removal. Version vectors, acknowledgements, membership epochs, and snapshot installation can establish that frontier. A wall-clock retention guess cannot. Replicas allowed to return indefinitely need a rejoin protocol that replaces stale state before tombstones can be collected safely.
State the Operation-Based Delivery Contract
An operation-based CRDT separates a local generator from an effector delivered to replicas. The generator validates against local state and creates an operation with the context needed for remote application. The effector mutates replica state. For convergence, effectors for concurrent operations must commute when delivery can order them differently.
A counter can broadcast uniquely identified increment operations. Addition commutes, but duplicate delivery overcounts unless the transport is exactly once or replicas remember operation IDs. An operation-based observed-remove set broadcasts tagged adds and removes carrying the set of observed tags. A remove must not be delivered before the causally prior adds whose tags it removes unless the representation can buffer or encode that missing context. Reliable causal broadcast is therefore commonly part of the contract.
Delivery guarantees are correctness conditions, not broker labels. Exactly-once processing across crashes needs durable deduplication applied atomically with the effect. Causal delivery needs sender context, ordering, or buffering. With only at-least-once unordered delivery, effectors must be idempotent and carry enough context, or the design should use state-based joins. Compaction likewise needs acknowledgements plus a membership and recovery model that prevents stale replicas from expecting discarded operations.
Delta-state CRDTs provide a middle ground: updates emit small joinable fragments merged with the same associative, commutative, idempotent join as full state. Deltas may be resent safely, and periodic full-state exchange repairs gaps. Discarding delta history still requires acknowledgement or version metadata because the algebra tolerates duplicates, not permanent omission.
Carry Causality Without Letting Metadata Drift
Unique tags often combine a replica incarnation and monotonically increasing local counter. Version vectors summarize the greatest counters observed from each replica. A dot identifies one event; a causal context summarizes events already incorporated. These structures let a CRDT distinguish a concurrent update from one whose author had observed an earlier value.
Causality is necessary for multi-value registers. If a write causally follows another write, it supersedes the earlier value. Concurrent writes remain as siblings because neither includes the other. A query can expose all concurrent values for domain reconciliation. Replacing that metadata with wall-clock comparison changes the product into a last-writer-wins register and can discard a causally later write when clocks skew.
A last-writer-wins register can still be a CRDT if each state carries a value plus a key from a deterministic total order and merge chooses the maximum key. max has the join laws. The hard part is semantics: arbitrary node-ID tie-breaks discard one concurrent value, and physical timestamps can be far from real order. Algebraic convergence does not endorse the timestamp source.
Metadata compaction must preserve comparison. Retiring vector components requires a membership epoch and a stale-message rule; reused IDs or regressed counters can make distinct dots collide. Persist identity state, assign new incarnations after uncertain recovery, and test imported snapshots against live causal contexts.
Match the CRDT to Product Invariants
Begin with operations users perform and conflicts they can create. Then choose explicit semantics for each concurrency case. For a set, decide add-wins, remove-wins, or retained conflicts. For a register, decide whether concurrent values can be shown, merged by domain logic, or deterministically discarded. For a counter, decide whether increments and decrements may proceed independently and whether bounds matter.
Some invariants are closed under merge. If every replica state satisfies the invariant and joining any two valid states also satisfies it, coordination-free updates may preserve it. A grow-only set whose elements all pass local schema validation is a simple example. Other invariants are not merge-closed. Two replicas can independently reserve the last available seat, each locally valid, and merge into an overbooked result.
Options include coordinating the conflicting operation, partitioning rights through an escrow scheme, redesigning the invariant, or accepting and repairing violations. An escrow counter can allocate decrement rights among replicas so each spends only local rights; transferring rights requires protocol support. That is more specific than using a positive-negative counter and checking the total later.
CRDTs also trade read simplicity for write availability. An observed-remove set carries tags and tombstones. A multi-value register asks a consumer to resolve siblings. A sequence carries positional metadata. Anti-entropy consumes bandwidth, and replicas need lifecycle rules. For data with one natural authority or infrequent offline writes, a conventional version check and explicit conflict response may be simpler.
Verify Laws, Networks, and Lifecycle
Test the algebra directly over valid reachable states. Property tests should generate states through legal mutators, then assert commutativity, associativity, and idempotence of merge. Assert each local update is inflationary under the defined partial order. For query-level equivalence, verify that different merge trees over the same states produce the same abstract value and, ideally, the same canonical internal state.
Use a deterministic replica simulator. Generate operations at several replicas, partition the network, duplicate and reorder snapshots or deltas, merge partial subsets, and finally deliver all information. Every replica must converge. Keep a sequential model for cases whose product semantics have a clear oracle. For the observed-remove set, include remove after observed add, concurrent add and remove, re-add with a fresh tag, duplicate merge, and a replica returning with old state.
Operation-based tests must exercise the promised transport contract and reject unsupported schedules. Deliver concurrent effectors in every order. Duplicate messages if deduplication is claimed. Crash between applying an operation and persisting its delivery marker to prove those changes are atomic. Delay a causally prior add and verify the system buffers, encodes context, or explicitly requires the transport to prevent that schedule.
Serialization is part of the state machine. Round-trip tags, counters, and causal contexts at boundary values. Test rolling upgrades that merge old and new encodings. A changed merge function can split the cluster into two algebras, so schema evolution needs compatibility rules and staged deployment. Never recycle a removed field if stale snapshots can still contain its old meaning.
Operate the anti-entropy protocol, not just the value. Measure convergence lag, pending peers, transfer size, merge failures, tombstone growth, causal-context size, snapshot age, and membership epoch. Alert when a replica cannot advance its acknowledgement frontier or repeatedly installs old snapshots.
Tombstone collection deserves a failure-injection test and a runbook. Prove that all active replicas crossed the stability frontier, compact, then attempt to reintroduce pre-frontier state. The system must reject it, force a fresh snapshot, or retain enough context to neutralize it. Time-based deletion without such a rejoin rule is a delayed resurrection bug.
CRDTs are rigorous when their promises stay narrow. The join laws make state exchange insensitive to order, grouping, and duplication. Inflationary updates preserve information. Operation-based designs instead rely on commuting concurrent effects and an explicit delivery contract. Causal metadata distinguishes supersession from concurrency, while product rules decide what either case means. With those pieces proven and tested, conflict-free replication is not a slogan about eventual consistency. It is a data type whose convergence follows from its algebra and whose limitations remain visible to its users.