Quilted

A delta-state CRDT: a value living in a join-semilattice.

piece is the join — the least-upper-bound of two states. It MUST satisfy the three lattice laws:

• idempotent a.piece(a) == a

• commutative a.piece(b) == b.piece(a)

• associative a.piece(b).piece(c) == a.piece(b.piece(c))

These laws are exactly what make convergence robust to kuilt's frame delivery semantics: a fabric may drop, duplicate, and reorder frames, but any two replicas that have absorbed the same set of states — in any order, with any repeats — compute the same value.

Operations are modeled as delta-mutators that return a Patch (a small fragment of the same lattice), which any replica absorbs with piece. The name nods to kuilt's quilting metaphor: a whole pieced from independent patches.

Two mutator shapes, one absorption path. A mutator may return either a Patch (the minimal lattice fragment for the change — BoundedCounter.trySpend, ORSet.add, ORMap.put, LWWMap.set) or a full new state S (LWWRegister.set, Gauge.observe). Both are absorbed by the identical piece join: a Patch is applied with piece(patch), and a returned full state is itself a valid join argument (a.piece(newState)).

Return a full state only when the whole state genuinely is the minimal delta. That is true of a single-cell type — an LWWRegister holds one tagged value, so there is nothing smaller to send. It is not true of a collection, however single-celled its per-key merge looks: an ORSet add touches one element, an ORMap put one key, an LWWMap set one cell, and returning the container would put every other element on the wire too. Those three return a Patch for exactly that reason, and their deltas are pinned byte-for-byte by the delta-mutator law X.piece(mᵟ(X)) == m(X) (#2044) — unconditionally for ORSet and ORMap, and for LWWMap exactly while the write's (timestamp, replica) tag dominates the key's current one, which is what its own tag-uniqueness rule already requires. Outside that domain no delta exists, because a delta is joined and a join can only move up the lattice (#2087).

An earlier version of this paragraph offered registers and maps together as the family whose whole state is already minimal. The maps were never in it, and that sentence is a large part of why every write shipped O(state) bytes for six months without anyone looking. When adding a type here, ask what one write costs on a large instance — not what the merge function looks like.

Type Parameters

Inheritors