Meaning comes before algebra

Patches describe three discovered capabilities: search, export, and audit. If true means admitted positive evidence and false means “not yet known,” then learning a fact moves upward and silence never retracts it. If the bits instead mean enable and disable commands, the chapter's algebra is wrong.

Order capability sets by subset: higher means containing at least as much evidence. Merge is union, the least upper bound. It is associative, so batching does not matter; commutative, so arrival order does not matter; and idempotent, so duplicates do not matter.

$$(a\sqcup b)\sqcup c=a\sqcup(b\sqcup c)$$ $$a\sqcup b=b\sqcup a$$ $$a\sqcup a=a$$

Finite combinations of these rewrites transform any delivery schedule with the same messages into the same result. That is the convergence proof. The identity is the empty evidence set.

Where the model stops

Retraction is not monotone in this carrier. “Disable export” is a command that may require authority, version order, or a richer lattice carrying tombstones. Do not translate product requirements until the laws work; first decide what the values mean and which observations merge must preserve.

Lessons

• Partial order may describe information rather than time.
• Join is the least state above both inputs.
• Associativity, commutativity, and idempotence remove batching, order, and duplicates.
• Retraction and competing commands require another model.

Practice

1. Prove the three laws for set union in words.
2. Discriminate last-writer-wins settings from grow-only capability evidence.
3. Transfer the merge to replicated cache keys or observed feature support.

Part VI moves from combining whole structures to carrying one focused location through them.

References

1. “Marc Shapiro et al., “Conflict-free Replicated Data Types”.” — convergence conditions and semilattice-based replicated data.
2. “Shapiro et al., “A comprehensive study of Convergent and Commutative Replicated Data Types”.” — expanded primary treatment of CRDT models and limits.