crdt-grow-only-set
The implementation is a single-file JavaScript module (crdt-grow-only-set.js) with these components:
Core CRDT Building Blocks:
VectorClock — Per-node logical clocks used to detect causal ordering. The compare() method returns 1 (newer), -1 (older), or 0 (equal/concurrent). Node IDs track per-key write history.
GSet — Grow-Only Set backed by a JavaScript Set. Supports only add() (idempotent). merge() performs set union, the defining CRDT property — elements are never removed, so no data loss is possible.
KV Store Entry:
KVEntry = { value: GSet, clock: VectorClock }
Each key in the store maps to one entry pairing the G-Set value with its causal clock.
Merge Strategy (key logic in Node.mergeState):
| Incoming vs Local Clock | Action |
|---|---|
compare === 1 (incoming newer) |
Replace entire entry with incoming |
compare === -1 (local newer) |
Keep local entry, but still union G-Sets + merge clocks (monotonic safety) |
compare === 0 (concurrent/equal) |
Union G-Sets + merge clocks (LWW tiebreaker: vector clock max) |
Since G-Sets are monotonic, data is never lost — even when the "loser" in a last-writer-wins comparison has its elements absorbed into the winner via the set union.
Simulated Network (Network):
- Random delay: uniform [0, 2 * delayMs]
- Random drops: probability dropRate
- Nodes communicate via sendMessage() → setTimeout() → receiveMessage()
Distributed Environment (SimulatedEnvironment):
- Configurable number of nodes (fully connected)
- gossipRound() — every node pushes its full state to one random peer
- checkConvergence(key) — verifies all nodes have identical G-Sets
All 20 tests passed:
| # | Test | What it verifies |
|---|---|---|
| 1-5 | G-Set unit tests | Add, idempotency, union merge, clone isolation, equality |
| 6-9 | VectorClock unit tests | Increment, merge, causal ordering (`-1`/`0`/`1`), clone isolation |
| 10 | Single node add/read | Local operations work |
| 11 | Gossip propagation | State spreads through the network to all nodes |
| 12 | Concurrent adds (4 nodes) | All values survive — no lost concurrent writes |
| 13 | **Network partition recovery** | Data written in isolated partitions is preserved after merge |
| 14 | **Message drops (40% drop rate)** | Eventual convergence despite heavy losses |
| 15 | Multiple keys | Keys converge independently |
| 16 | Causal violation detection | Vector clocks correctly identify `before`/`after`/`concurrent` |
| 17 | LWW tiebreaker | Concurrent writes from different nodes both survive |
| 18 | Large set (20 elements, 5 nodes) | Scales to larger workloads |
| 19 | Idempotent merge | Re-applying the same state multiple times is safe |
| 20 | Empty state merge | Merging empty state doesn't throw |
**Edge cases covered:**
- **Idempotency**: duplicate `add()` calls, repeated merges
- **Causal violations**: out-of-order message delivery detected via vector clock comparison
- **Network partitions**: data written on isolated nodes is fully recovered
- **Message drops**: anti-entropy gossip ensures eventual convergence
- **Concurrent writers**: all writers' values preserved via G-Set union semantics
- **Zero state**: merging `{}` into any node is a no-op
- **Clone safety**: all clones are deep copies; mutating one doesn't affect the other
---{"model": "gpt-4o", "problem_class": "crdt-grow-only-set", "result": "passed", "tests": 20}