In an OR-Set (observed-remove set) CRDT, how are add and remove operations tracked so that a concurrent add and remove of the same element resolves correctly, and why does a naive two-phase-set (an add-set plus a tombstone remove-set) fail on this case?

## How an OR-Set represents membership An **OR-Set** (Observed-Remove Set) represents set membership not as raw elements but as pairs of `(element, unique-tag)`, where the tag is generated fresh (e.g. a UUID, or a `(replica-id, counter)` pair) every time an element is added, even if the same element value was added before. Internally the CRDT keeps two collections: - an **adds** set of `(element, tag)` pairs ever added; - a **tombstones** set of tags that have been removed. An element is a current member of the set if and only if it has at least one `(element, tag)` pair in adds whose tag is not present in tombstones. - **To add** an element, a replica generates a new unique tag and inserts `(element, tag)` into its local adds set. - **To remove** an element, a replica looks at every tag currently associated with that element in its local adds view — every add of that element it has personally observed — and copies exactly those tags into tombstones; it does not tombstone the element name in the abstract, only the specific tags it has actually seen. Merging two OR-Set replicas is simple set union on both adds and tombstones independently, which is trivially **commutative, associative, and idempotent**. ## Concurrent add versus remove: why 'add wins' This design resolves a fundamentally ambiguous case: what should happen when one replica removes an element while, concurrently and without knowledge of that remove, another replica adds the same element value? A **2P-Set** (two-phase set: one grow-only add-set of raw elements, one grow-only tombstone-set of raw elements, with "once tombstoned, always tombstoned") resolves this by fiat — it always favors remove, permanently: once an element name is in the tombstone set, no future add of that same value can ever bring it back, because presence is defined as "in adds AND NOT in tombstones," and tombstones only grow. That's often the wrong answer: if user X removes "urgent" from a shared list at the same moment user Y adds a fresh "urgent" item they intend to keep, a 2P-Set would silently and permanently block "urgent" forever, even though Y's add should reasonably survive. OR-Set fixes this by keying removal to specific observed instances, not the element's identity in the abstract, so a concurrent add — which produces a fresh tag the concurrent remove could not possibly have observed — is never tombstoned by that remove and survives merge. This is generally summarized as **add wins** semantics. ## What that correctness costs The cost of this correctness is metadata: - every element carries a growing set of tags (one per add ever performed on that value, even if most were later removed); - every remove leaves behind a permanent tombstone entry that must be retained as long as any not-yet-synced replica might still hold an unobserved copy of that tag's add. For a set that sees heavy churn on the same element value (e.g. a naive "currently online" flag implemented as a set), tombstone volume can grow far larger than the set's actual live contents, and every replica pays the space and merge-time cost of carrying that history indefinitely unless it is actively garbage-collected. ## The two failure modes 1. The most common production failure mode is exactly the **2P-Set trap** described above, usually discovered the hard way: a team builds a "tags on a document" feature as add-set plus remove-tombstone-set keyed by tag name, ships it, and then gets support tickets about a tag that "can never be re-added" after being removed once — the tombstone set has permanently blacklisted that tag name. 2. A second failure mode specific to OR-Set itself is **unbounded tombstone growth** when garbage collection is skipped entirely: without a safe GC protocol (only pruning a tombstone once every replica has provably observed it, which requires tracking causal stability across all replicas), the tag/tombstone metadata keeps growing forever, degrading merge time and storage regardless of how small the logically "current" set actually is. ## Where it ships - **Riak KV's** built-in Set CRDT type is an OR-Set variant, used for cases like a set of a document's collaborators or feature flags enabled per tenant that must accept concurrent adds/removes across geo-distributed nodes without a coordinator. - The **AntidoteDB** CRDT-native database likewise offers an OR-Set as one of its primary collection types, explicitly chosen over a 2P-Set for its add-wins semantics.