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.
The structures from this family that fit the shared gauge rig run
below on watershed’s Gleam kernels. Structures with dedicated
interactions link to their own demos. Pending edits print in
magenta; once the sequencer stamps
an SN, every replica lands the same ink
state. The picker switches among the loaded views, which share one
ordered stream.
Nudge a value, race a concurrent write, or stretch the link latency
to watch each merge rule hold.
1 · local edit prints in magenta
2 · the sequencer stamps it with an SN
3 · every client lands the same ink state
Merge rule: last write wins. Race two writes to the
same key and the op the sequencer stamps later overwrites the earlier
one, identically on every replica.
Merge rule: increments commute. Race two increments
and both apply. The counter converges on the sum; nothing is
overwritten.
Merge rule: grow-only max per replica. Each client owns
one monotonically increasing tally. Race two inspections or deliver a
delta twice: replicas converge by keeping the maximum count seen for
each author.
Merge rule: deltas join a lattice. Every update
travels as a CRDT delta; merging is commutative and idempotent. Race
it, resend it, deliver it twice: it counts exactly once, and the
balance converges on fill − cut.
Merge rule: first writer wins. A claim commits only
if the slot is still unclaimed when the sequencer stamps it (or its
reference SN matches the holder’s exactly). Nothing prints
optimistically: a filed claim is invisible, even to you, until it
round-trips as won or lost.
Merge rule: add-wins, observed-remove. A strike only
removes stockpile entries the striker had seen. Race a strike against a
concurrent delivery and the row survives, with every logged yard.
Re-opening a struck pile brings its ledger back.
Merge rule: add-wins, observed-remove. Clearing a marker
removes only the add tags this replica had observed. Race a clear against
a concurrent re-mark and the marker remains present because the fresh tag
was unseen by the clear.
Merge rule: grow-only union. Marking a benchmark is a
permanent fact. Race two marks or deliver one twice: the registry only
grows, and duplicate deltas are absorbed.
Merge rule: tombstone wins. A retired marker can never
become active again. Race a re-place against a retire: both replicas keep
the tombstone, and duplicate retire deltas are absorbed.
Merge rule: atomic plus retained versions. A write that
knew the current atomic sequence wins the linearizable slot. Concurrent
losers still append a version, so LWW reads can intentionally diverge from
atomic reads.
Merge rule: FIFO by sequence. Adds enter the queue in
server order. Acquires remove the front item when their op sequences; a
racing acquire may come back empty because the earlier SN already took it.
Merge rule: one assignee, FIFO waiters. Volunteers join
a per-task queue in sequenced order. The first connected volunteer owns the
task; abandon promotes the next waiter, and complete clears the queue.
Merge rule: quorum acceptance. A set first prints as
pending with a frozen signoff list. It becomes accepted only after every
connected client signs off, or leaves drain the list.
Client A
0 pending
Shared map replica on Client A
mill-race
24
kettle-run
61
low-ford
42
sandbags-placed
earthwork-balance · yd³
fill Σ
74
cut Σ
30
cutfill
inspection-count
A Σ
0
B Σ
0
C Σ
0
Claims replica on Client A
north-levee
spillway-gate
pump-house
OR-map stockpile ledger replica on Client A
spoil-north
borrow-pit-7
wash-fill
OR-set field marker roster replica on Client A
north-stake
sluice-tag
borrow-flag
G-set permanent benchmark registry replica on Client A
BM-17
BM-22
BM-31
2P-set retired marker ledger replica on Client A
stake-3
gate-pin
silt-flag
RegisterCollection replica on Client A
register
atomic
LWW
revise
north-bench
gate-setpoint
pump-mode
OrderedCollection replica on Client A
sheet
state
op
queue
held jobs
PactMap replica on Client A
pact
accepted
pending
op
datum-grid
gate-policy
inspection-window
TaskManager replica on Client A
task
assigned
waiters
op
sluice-inspection
pump-watch
crest-walk
Client B
0 pending
link cut — ops park locally until the link is restored
Shared map replica on Client B
mill-race
24
kettle-run
61
low-ford
42
sandbags-placed
earthwork-balance · yd³
fill Σ
74
cut Σ
30
cutfill
inspection-count
A Σ
0
B Σ
0
C Σ
0
Claims replica on Client B
north-levee
spillway-gate
pump-house
OR-map stockpile ledger replica on Client B
spoil-north
borrow-pit-7
wash-fill
OR-set field marker roster replica on Client B
north-stake
sluice-tag
borrow-flag
G-set permanent benchmark registry replica on Client B
BM-17
BM-22
BM-31
2P-set retired marker ledger replica on Client B
stake-3
gate-pin
silt-flag
RegisterCollection replica on Client B
register
atomic
LWW
revise
north-bench
gate-setpoint
pump-mode
OrderedCollection replica on Client B
sheet
state
op
queue
held jobs
PactMap replica on Client B
pact
accepted
pending
op
datum-grid
gate-policy
inspection-window
TaskManager replica on Client B
task
assigned
waiters
op
sluice-inspection
pump-watch
crest-walk
Client C
0 pending
Shared map replica on Client C
mill-race
24
kettle-run
61
low-ford
42
sandbags-placed
earthwork-balance · yd³
fill Σ
74
cut Σ
30
cutfill
inspection-count
A Σ
0
B Σ
0
C Σ
0
Claims replica on Client C
north-levee
spillway-gate
pump-house
OR-map stockpile ledger replica on Client C
spoil-north
borrow-pit-7
wash-fill
OR-set field marker roster replica on Client C
north-stake
sluice-tag
borrow-flag
G-set permanent benchmark registry replica on Client C
BM-17
BM-22
BM-31
2P-set retired marker ledger replica on Client C
stake-3
gate-pin
silt-flag
RegisterCollection replica on Client C
register
atomic
LWW
revise
north-bench
gate-setpoint
pump-mode
OrderedCollection replica on Client C
sheet
state
op
queue
held jobs
PactMap replica on Client C
pact
accepted
pending
op
datum-grid
gate-policy
inspection-window
TaskManager replica on Client C
task
assigned
waiters
op
sluice-inspection
pump-watch
crest-walk
Sequencer
Loading
booting watershed kernels…
Latency and jitter affect simulated arrival order; animation speed
changes playback only. “Ops in flight” counts every hop still
travelling: one client → sequencer leg, then one
sequencer → replica leg per client.
The live demo couldn’t start: it runs watershed’s runtime counter channel
and kernels as compiled JavaScript modules, and this browser didn’t load
them. The rest of the page works fine without it. Reload the page to retry.
No. 01
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
No. 02
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
No. 03
OrSet
CRDT
or_set_kernel
A set where add, remove, and add-again all work: the everyday choice.
An observed-remove set fixes the 2P-set’s fatal flaw: 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 is why the OR-set is the workhorse removable set across collaborative apps.
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
Magenta indicates revisions not yet field-checkedConvergence by server sequencing — assumptions on the models sheettylerbutler.com