ORSet

An observed-removal set (OR-Set) is a conflict-free replicated data type (CRDT) designed to implement a distributed set that supports add and remove operations with strong convergence guarantees. It uses the observed-removed semantics to ensure that replicas eventually converge to the same state despite concurrent updates and network delays.

In an OR-Set, the state is typically represented by two components: a collection of add-tags and a collection of removed-tags. For each element e, an addition is represented by a unique tag (e, t). The logical contents of the set are the elements that have at least one addition tag that has not been removed. A remove operation marks specific add-tags as removed by recording those tags in the removed-tags component. This means removing an element requires removing the particular add-tags associated with it, not just the element name.

Merging states across replicas is straightforward: the adds and removes are merged by taking the union of their respective tag sets. After merging, an element remains present if there exists at least one add-tag for that element that has not been removed. Because adds and removes are tracked with unique identifiers, the order of updates and the timing of synchronization do not affect eventual consistency.

A notable drawback of the basic OR-Set is unbounded growth, since each add creates a new tag that may need to be remembered indefinitely to preserve correctness. Practical deployments may implement garbage collection of tags once all replicas have observed the corresponding removals, or use variants of CRDT sets that trade off some functionality for reduced metadata, such as two-phase or less granular approaches. OR-Set remains a foundational example of how CRDTs handle list-like or set-like structures with concurrent updates.