CRDT Foundations: Counters, Sets, Registers, Monotonic State, and Convergence

1. CRDT means the conflict semantics are designed into the data type

A Conflict-Free Replicated Data Type (CRDT) is constructed so replicas can accept certain updates independently and later converge without coordination, assuming the CRDT's delivery/state assumptions hold. There are two broad families. State-based (convergent) CRDTs periodically merge replica states using a join operation. Operation-based (commutative) CRDTs disseminate operations under delivery assumptions chosen by the design.

The key phrase is designed data type. Renaming an arbitrary shopping-order object “CRDT” does not make payment, inventory, and shipping invariants merge safely.

2. State-based merge needs algebraic safety

For a state-based CRDT, the merge behaves like a least-upper-bound in a join-semilattice. At the practical level, the merge should be commutative (merge(A,B)=merge(B,A)), associative, and idempotent (merge(A,A)=A). Those properties let replicas receive states repeatedly and in different groupings without changing the eventual result.

A grow-only counter (G-Counter) stores one non-decreasing component per replica. A replica increments only its own component. Merge takes the component-wise maximum; value is the sum. A positive-negative counter (PN-Counter) uses two grow-only counters, one for increments and one for decrements, then subtracts their totals.

3. Removes are harder than adds

A grow-only set converges by union, but it cannot remove. A two-phase set records additions and removals but does not allow re-adding a removed element. An Observed-Remove Set (OR-Set) attaches unique identities to add operations. A remove only removes add-tags it has observed, so a truly concurrent new add can survive. Different CRDT set variants deliberately choose different concurrent add/remove semantics.

This metadata is the cost of preserving intent. Garbage-collecting tags or tombstones safely requires causal/stability knowledge; deleting them too early can resurrect elements after delayed replicas reappear.

4. AtlasMart lab: merge counters and an observed-remove set

The lab builds a state-based G-Counter, derives a PN-counter value, then implements a small OR-Set-style simulator with unique add tags and an observed-remove set. It verifies commutativity/idempotence for the deterministic merges.

from copy import deepcopy

print("STATE-BASED G-COUNTER")
def gc_inc(state, replica, n=1):
    state[replica] = state.get(replica, 0) + n

def gc_merge(a, b):
    return {k: max(a.get(k, 0), b.get(k, 0)) for k in set(a) | set(b)}

def gc_value(state): return sum(state.values())

A = {"A": 0, "B": 0}; B = deepcopy(A)
gc_inc(A, "A", 3); gc_inc(B, "B", 2)
print("before merge A:", A, "B:", B)
m1 = gc_merge(A, B); m2 = gc_merge(B, A)
print("merge A,B:", m1, "value:", gc_value(m1))
print("commutative:", m1 == m2)
print("idempotent:", gc_merge(m1, m1) == m1)

print("\nPN-COUNTER = TWO G-COUNTERS")
p = {"A": 4, "B": 1}; n = {"A": 1, "B": 2}
print("value:", gc_value(p) - gc_value(n), "P:", p, "N:", n)

print("\nOBSERVED-REMOVE SET WITH UNIQUE ADD TAGS")
def or_add(state, element, tag):
    state["adds"].setdefault(element, set()).add(tag)
def or_remove(state, element):
    state["removes"].update(state["adds"].get(element, set()))
def or_merge(a, b):
    out = {"adds": {}, "removes": set(a["removes"]) | set(b["removes"])}
    for e in set(a["adds"]) | set(b["adds"]):
        out["adds"][e] = set(a["adds"].get(e, set())) | set(b["adds"].get(e, set()))
    return out
def or_value(state):
    return sorted(e for e,tags in state["adds"].items() if tags - state["removes"])

s0 = {"adds": {}, "removes": set()}
or_add(s0, "sku-7", "A:1")
Aset = deepcopy(s0); Bset = deepcopy(s0)
or_remove(Aset, "sku-7")       # removes the observed A:1 add
or_add(Bset, "sku-7", "B:1")   # concurrent new add
sm = or_merge(Aset, Bset)
print("A value:", or_value(Aset), "B value:", or_value(Bset))
print("merged add-wins-for-concurrent-new-tag value:", or_value(sm))
print("merge idempotent:", or_value(or_merge(sm, sm)) == or_value(sm))

print("\nREGISTER WARNING")
print("a last-write-wins register can converge, but convergence does not mean both business edits were preserved")
print("CRDT merge laws apply to the designed state/operations, not arbitrary objects by naming convention")

5. Convergence does not preserve every business invariant

A PN-counter can converge perfectly while inventory becomes negative if disconnected regions each decrement against the same logical stock. A set can converge while an unauthorized principal adds itself. A register can converge while losing one user's text edit. CRDTs remove a class of coordination needed for convergence; they do not remove authorization, bounded-resource, uniqueness, referential, or workflow invariants.

Where an invariant is not closed under the CRDT merge, coordination, escrow/allocation, invariant-preserving decomposition, or a different data type is still required.

6. Deliberately wrong approach: “all operations commute if retries are idempotent”

Idempotence means repeating an operation does not change the intended effect after the first application. Commutativity means changing the order of two distinct operations does not change the result. They are different properties. set price=90 can be idempotent but does not commute with apply 10% discount. CRDT operation designs need the exact delivery and algebraic assumptions they claim.

7. Production judgment and bridge

Choose a CRDT when disconnected/low-coordination updates are valuable, the data type's conflict semantics match the product, and the metadata/storage cost is understood. Test convergence under duplicate, reordering, delay, restart, membership changes, and metadata compaction. Observe state size, tombstone/tag growth, merge CPU, anti-entropy lag, divergent-state duration, and invariant violations outside the CRDT.

The final chapter lesson turns to a related but distinct property: idempotency. It is often the right response to duplicate delivery and ambiguous retries even when the underlying data is not a CRDT.

References

Foundational claims use primary research/specifications where practical. Product documentation is used only as a current implementation example and is not required for the mandatory labs.

• Shapiro et al. — Conflict-Free Replicated Data Types — Foundational CRDT research report/paper describing convergent and commutative replicated data types.
• Shapiro et al. — A Comprehensive Study of CRDTs — Detailed CRDT taxonomy and conditions for convergence.
• Preguiça et al. — A Commutative Replicated Data Type for Cooperative Editing — Early operation/commutativity-based replicated data type work.
• Bieniusa et al. — An Optimized Conflict-Free Replicated Set — Set CRDT design and metadata considerations relevant to add/remove semantics.