State-based CRDTs: merge information with a join

A join-semilattice supplies a partial order and a least upper bound for every pair of states. Its join is commutative, associative, and idempotent. Commutativity tolerates reversed arrival order, associativity tolerates different grouping, and idempotence tolerates repeated delivery of the same state. These laws explain why sending a whole state twice need not count its contents twice. Choosing addition as the merge for already-accumulated totals usually fails this requirement: merging the same state twice increases the total again.

Local updates must also be inflationary in the chosen state order, and communication must eventually carry the relevant updates to correct replicas. Algebra cannot repair a message that is lost forever without any later state containing its information. Similarly, merely labeling an arbitrary JSON merge as a CRDT does not establish a partial order or its laws. State the payload, update, merge, query, and delivery assumptions, then test the laws on histories as well as individual sample values.

For a fixed-membership grow-only counter, store one nonnegative component per replica. Replica i increments only its own component. Merge takes componentwise maxima, while the visible counter is the sum. A transferred component is an accumulated count from that actor, not another increment to add on arrival. This representation lets a receiver learn a newer prefix without counting the older prefix twice. Stable replica identities and nondecreasing counters remain essential; restarting from zero under the same identity would break the accounting.

To support decrements, one standard construction keeps separate grow-only positive and negative vectors and subtracts their sums when queried. The visible value can decrease even though each internal component only increases. This illustrates why monotonicity must name the state order. It does not automatically make a bounded counter safe: two disconnected replicas could each spend the last available unit. Bounds require an appropriate design such as escrow rights or coordination, not a wish that convergent arithmetic enforces all numeric constraints.

Generate histories with duplicate state exchange, delayed stale states, concurrent increments, and different merge groupings. Compare both internal states and observable queries after all information arrives. Then test the product’s actual requirements: reset behavior, actor retirement, permissions, and bounds are not answered by the three merge laws alone. Delta-state techniques can reduce transmitted payload, but their deltas and propagation protocol must preserve the same information requirements. Sending an arbitrary numeric difference is not enough to inherit the original state proof.

Use the modular lab to construct a counterexample to naive numeric monotonicity. Reset, set m=8 and a=3, predict residues 0,3,6,1, then Step through three transitions. The visible residue decreases from six to one even though another addition occurred. This finite additive orbit is not a G-counter or a join implementation. Its purpose is to force you to name the order: ordinary numeric order on residues does not describe accumulating knowledge, while the CRDT’s componentwise metadata order does.