observed-remove-crdt
The OR-Set CRDT is implemented in ~/or-set.js. The design uses add-wins semantics — every add(element) creates a unique tag (replicaId, counter) stored in addSet, and remove(element) moves all of that replica's observed tags for the element into removeSet. An element is present iff it has at least one add-tag that is not in the remove set.
Key design decisions:
Tags as (replicaId, counter) — Each add generates a globally unique tag from the local replica id and a monotonically increasing counter, also tracked in the version vector.
Version vectors for causal context — Each replica maintains versionVector: { replicaId → maxCounter }. This enables incremental delta computation: diff(other) returns only tags whose counter exceeds the other replica's version vector entry.
Union-based merge — merge(other) takes the set union of both addSet and removeSet (per element), and element-wise max of version vectors. This is the least-upper-bound in the join-semilattice, guaranteeing Strong Convergence.
Anti-entropy gossip — diff(other) computes only the tags the other replica hasn't seen. applyDelta(delta) applies those changes without full-state exchange.
Add-then-remove convergence — When A adds x (tag A:1) then removes it, the tag A:1 goes into removeSet. After sync, B sees A:1 in both sets, so x is absent. If B concurrently added x (tag B:1), that tag survives — add-wins for concurrent operations.
const { ORSet } = require('./or-set');
const a = new ORSet('replica-1');
const b = new ORSet('replica-2');
a.add('apple');
b.add('banana');
// Gossip: each sends what the other lacks
b.applyDelta(a.diff(b)); // b learns about 'apple'
a.applyDelta(b.diff(a)); // a learns about 'banana'
a.remove('apple');
b.applyDelta(a.diff(b)); // b learns about the removal
console.log(b.values()); // ['banana']
**26 tests** all pass. The test suite covers: | Category | Tests | What it proves | |---|---|---| | **Basic ops** | 6 | Single-replica add/has/remove/add-again, multiple elements, duplicate adds, remove non-existent | | **Two-replica merge** | 5 | Independent adds converge; add-then-remove converges to removed; concurrent add/remove → add-wins; causal ordering resilience | | **Anti-entropy gossip** | 4 | Empty diff for identical replicas; diff detects missing tags; applyDelta catches up; three-replica gossip convergence | | **Network partition** | 2 | Concurrent operations on partitioned replicas heal correctly; full add-remove-add across 3 replicas converges | | **Serialization** | 2 | toJSON/fromJSON round-trip preserves all state | | **Edge cases** | 5 | Empty set, merge with empty, concurrent remove both sides, no double-count after multiple merges, invalid replica ID rejection | | **Stress** | 2 | 100 elements converge; remove half after merge | **Key edge case verified:** Partition where A removes `x` while B concurrently adds `x` — after healing, both converge to `x` present (B's add tag survives), confirming **add-wins** semantics. ---
{"model": "claude-4", "problem_class": "observed-remove-crdt", "result": "passed", "tests": 26}The OR-Set CRDT is implemented in ~/or-set.js. The design uses add-wins semantics — every add(element) creates a unique tag (replicaId, counter) stored in addSet, and remove(element) moves all of that replica's observed tags for the element into removeSet. An element is present iff it has at least one add-tag that is not in the remove set.
Key design decisions:
Tags as (replicaId, counter) — Each add generates a globally unique tag from the local replica id and a monotonically increasing counter, also tracked in the version vector.
Version vectors for causal context — Each replica maintains versionVector: { replicaId → maxCounter }. This enables incremental delta computation: diff(other) returns only tags whose counter exceeds the other replica's version vector entry.
Union-based merge — merge(other) takes the set union of both addSet and removeSet (per element), and element-wise max of version vectors. This is the least-upper-bound in the join-semilattice, guaranteeing Strong Convergence.
Anti-entropy gossip — diff(other) computes only the tags the other replica hasn't seen. applyDelta(delta) applies those changes without full-state exchange.
Add-then-remove convergence — When A adds x (tag A:1) then removes it, the tag A:1 goes into removeSet. After sync, B sees A:1 in both sets, so x is absent. If B concurrently added x (tag B:1), that tag survives — add-wins for concurrent operations.
const { ORSet } = require('./or-set');
const a = new ORSet('replica-1');
const b = new ORSet('replica-2');
a.add('apple');
b.add('banana');
// Gossip: each sends what the other lacks
b.applyDelta(a.diff(b)); // b learns about 'apple'
a.applyDelta(b.diff(a)); // a learns about 'banana'
a.remove('apple');
b.applyDelta(a.diff(b)); // b learns about the removal
console.log(b.values()); // ['banana']
**26 tests** all pass. The test suite covers: | Category | Tests | What it proves | |---|---|---| | **Basic ops** | 6 | Single-replica add/has/remove/add-again, multiple elements, duplicate adds, remove non-existent | | **Two-replica merge** | 5 | Independent adds converge; add-then-remove converges to removed; concurrent add/remove → add-wins; causal ordering resilience | | **Anti-entropy gossip** | 4 | Empty diff for identical replicas; diff detects missing tags; applyDelta catches up; three-replica gossip convergence | | **Network partition** | 2 | Concurrent operations on partitioned replicas heal correctly; full add-remove-add across 3 replicas converges | | **Serialization** | 2 | toJSON/fromJSON round-trip preserves all state | | **Edge cases** | 5 | Empty set, merge with empty, concurrent remove both sides, no double-count after multiple merges, invalid replica ID rejection | | **Stress** | 2 | 100 elements converge; remove half after merge | **Key edge case verified:** Partition where A removes `x` while B concurrently adds `x` — after healing, both converge to `x` present (B's add tag survives), confirming **add-wins** semantics. ---
{"model": "claude-4", "problem_class": "observed-remove-crdt", "result": "passed", "tests": 26}