OR-Set CRDT

An OR-Set (Observed-Remove Set) is a replicated set where a concurrent add and remove of the same element converge with the add winning, achieved by tagging every add with a globally unique id and tombstoning only the tags a remove actually observed. It is a CRDT — a data type that many replicas can edit offline and later merge into the same answer with no coordination and no conflicts. The trick that makes "delete" safe under concurrency is giving each add its own identity, so a remove can retire the exact copies it saw while leaving anyone else's fresh add untouched.

Build a factory orSetCrdt(nodeId) that returns one replica of the set. nodeId identifies this replica; every add mints a fresh tag from nodeId and a per-replica counter, so two replicas never generate the same tag.

Signature

type Tag = string; // `${nodeId}#${counter}` — globally unique, deterministic
type State = { adds: [Tag, string][]; removes: Tag[] };

function orSetCrdt(nodeId: string): {
  add(elem: string): void;       // stamp elem with a fresh unique tag
  remove(elem: string): void;    // tombstone the tags currently observed for elem
  has(elem: string): boolean;    // true if any tag for elem is not tombstoned
  values(): string[];            // every live element, deduped
  merge(other: { state(): State }): void; // union both adds and both removes
  state(): State;                // canonical, serializable snapshot
};

Examples

const cart = orSetCrdt('phone');

cart.add('milk');
cart.has('milk'); // true
cart.remove('milk');
cart.has('milk'); // false
cart.add('milk'); // re-add works — a fresh tag, not the tombstoned one
cart.has('milk'); // true

const a = orSetCrdt('laptop');
const b = orSetCrdt('phone');

a.add('milk');
b.merge(a); // both replicas now know about milk

a.remove('milk'); // laptop removes it...
b.add('milk'); // ...while phone concurrently re-adds it

a.merge(b);
b.merge(a);
a.has('milk'); // true — the concurrent add wins
b.has('milk'); // true — both replicas converge to the same answer

Notes

• Unique tags — every add stamps the element with a fresh id built from nodeId and a per-replica counter. Never use Math.random or Date.now; ids must be deterministic and never repeat.
• Observed removes — remove tombstones only the tags currently in this replica's adds. A concurrent add elsewhere carries a tag you have not observed, so it survives.
• Add wins — with a concurrent add and remove of the same element, the element is still present after both replicas merge.
• Merge is a union — merge unions the two adds maps and the two removes sets. That union is commutative, associative, and idempotent.
• Elements are primitives — store strings or numbers; equality is by value. Do not worry about deep object elements or garbage-collecting old tombstones.