watershed Collaborative data structures for Gleam

← watershed · Data structures / Sets

Sets

Lists of things, as people add and remove at the same time.

A set looks simple until two clients disagree about whether an element belongs. These are a short course in that problem: the more removal you want, the more causal bookkeeping you pay for.

Start with add-only union, add irreversible tombstones, then reach the observed-remove set that lets you add, remove, and add again while staying convergent.

GSet

CRDT
g_set_kernel

A set you can only add to (the simplest one that always agrees).

The simplest set CRDT. Elements can be added but never removed. Merging two replicas is a plain union (commutative, associative, and idempotent), so adds arrive in any order, any number of times, and everyone converges on the same membership.

Removal is not expressible, which is what makes a G-set trivially correct. When you need removal, you layer tombstones on top: the 2P-set and OR-set below.

Best for

  • Append-only registries: recorded events, observed device IDs, seen keys
  • Deduplicated event logs where membership only ever grows
  • The base layer for removable set CRDTs
Merge rule
an add-only set; once something is in, it stays, and merging is a plain union
Optimistic behavior
your addition shows in magenta until it's confirmed
Summary shape
the confirmed set reloads as a permanent record
Model
Conflict-free replicated data type: converges by merge

TwoPSet

CRDT
two_p_set_kernel

A set you can remove from, but a removed item never comes back.

A two-phase set layers a grow-only set of tombstones over a grow-only set of adds. An element is a member when it is in the add-set and absent from the tombstone-set.

Both halves only grow, so merge is two unions and convergence is guaranteed. The trade-off is stark: once removed, an element can never be re-added, because the tombstone always wins. Concurrent add-versus-remove resolves remove-wins on every replica. A reset needs a fresh set rather than a shrinking op.

Best for

  • Membership where retirement is final: revoked credentials, decommissioned assets
  • Audit or compliance sets where a removal must never silently reverse
  • Cases where remove-wins is correct and re-adding is genuinely disallowed
Merge rule
supports removal, but once an item is removed it can never be added again
Optimistic behavior
adds and removals show in magenta until they're confirmed
Summary shape
current items and removed ones reload together
Model
Conflict-free replicated data type: converges by merge

OrSet

CRDT
or_set_kernel

Add it, remove it, add it again: unlike a 2P-set, this one can bring an item back.

An observed-remove set gets around the 2P-set's one-way removal: you can add, remove, and add again. Every add attaches a unique causal tag (a dot), and a remove only tombstones the tags it has actually observed.

If one client removes an element while another concurrently adds it under a fresh tag, the new tag survives and the element stays (add-wins). That bookkeeping lets an item be removed and later re-added without giving up add-wins concurrency.

Best for

  • Collaborative selections, tags, labels, and shopping carts
  • Durable roster membership edited concurrently by many clients; transient online presence belongs in ripples
  • Any removable set where re-adding a just-removed item must work
Merge rule
add, remove, and add again all work; if an add and a remove race, the add wins
Optimistic behavior
your change overlays the list in magenta until it's confirmed
Summary shape
current members and their removal history reload intact
Model
Conflict-free replicated data type: converges by merge