Observed-remove sets: remove the additions you actually saw

Represent an add as a pair of an element and a globally unique tag, such as a stable actor identity plus a never-reused counter. Adding the same element twice creates two tags even though the user-visible set shows it once. A remove records the tags for that element currently visible at its origin. It cannot name a concurrent addition it has not seen. Reusing tags after a crash breaks the interpretation by making a genuinely new addition look like an already removed historical one.

For a simple state-based teaching construction, keep a grow-only set A of all learned add pairs and a grow-only tombstone set T of removed tags. Merge both by union. An element is visible when at least one learned add tag for it is not tombstoned. This stores more metadata than optimized implementations, but makes the mechanism explicit. A missing visible element and a missing historical add are different facts; deleting the latter from storage without a justified compaction rule can change future merges.

Suppose A adds a label with tag A1 and later removes it, while a disconnected B independently adds the same label with tag B1. A’s remove can tombstone A1 but not B1. After merging, B1 remains live and the label is visible. If A first observes both additions and then removes the label, both tags are tombstoned and it becomes absent. Thus add wins applies to the concurrent unseen add; a causally later observed remove can remove all currently known additions.

In an operation-based implementation, the remove effect must carry the observed tags or equivalent causal information. Replacing it with delete whatever the receiver currently sees can erase a concurrent addition and produce different outcomes under different delivery orders. Optimized observed-remove sets can encode removed history through causal contexts rather than retaining an explicit tombstone for every tag. Their merge rules are not obtained by simply throwing tombstones away from this teaching construction. Use the algorithm’s actual context and dot rules when implementing the optimization.

A collaborative favorites list may reasonably retain an item someone added while another person removed an older instance. An access-control revocation may demand a different policy: allowing an unseen concurrent grant to survive could violate expectations. CRDT convergence does not choose that policy for you. Distinguish add-wins, remove-wins, and permanently removed two-phase sets before deciding which type a field needs. Test histories using operation identities and causal observations rather than only the final human-readable set.

The modular lab provides a concrete warning about reusing finite tag counters. Reset, set m=4 and a=1, predict 0→1→2→3→0, then Step four times. A repeated residue cannot uniquely identify a fresh addition after wraparound. This is an additive orbit, not an OR-Set: there are no elements, tag maps, or remove effects in the diagram. The actual membership trace remains the explicit A and T calculation. Real tags need a non-reuse discipline or a proven epoch protocol.