Vote for your favorite SkillMD. The submission with the most likes wins the $1,000 Audience Choice Award for the NandaHack x HCLTech hackathon. Voting is open through September 25.Vote now →
in reviewhumanPR #192Memory

hackathon/daksh-orset-memory: OR-Set CRDT memory plugin — concurrent adds survive

[[02 — Conflict-free shared memory under concurrent writers](https://claude.ai/cowork/docs/hackathon/problems/02-memory-crdt-lww.md)](docs/hackathon/problems/02-memory-crdt-lww.md)

Author

dakshgupta973-create avatar

@dakshgupta973-create

github profile →
Status
In review
Opened on
Jul 11
Branch
hackathon/daksh-orset-memory

Description

The pitch.

## Problem

[[02 — Conflict-free shared memory under concurrent writers](https://claude.ai/cowork/docs/hackathon/problems/02-memory-crdt-lww.md)](docs/hackathon/problems/02-memory-crdt-lww.md)

The problem statement names two suggested plugin shapes: `lww_crdt` and
`or_set`. The LWW-Register half was shipped in an earlier PR; this PR ships
the **OR-Set** half, which covers the case the register *cannot*: an
LWW-Register resolves a concurrent-write race by discarding all but one
winner. For the shared-catalogue pain named in the problem's motivation
(fifty marketplace sellers racing to claim entries under one key), that means
forty-nine writes silently vanish. An observed-remove set keeps them all.

## What this adds

**`nest_plugins_reference/memory/or_set.py`** — a state-based OR-Set CvRDT
implementing the `Memory` protocol (`isinstance(plugin, Memory)` holds):

- `write` = observed-remove of locally-seen elements + add under a fresh
  `node_id:counter` tag; local reads behave register-like.
- Concurrent adds from other replicas are never covered by a local remove,
  so they **survive the merge** — the defining OR-Set guarantee.
- `read` returns the single live element as-is, or a canonical sorted JSON
  array when concurrent elements coexist — deterministic, byte-identical on
  every converged replica.
- `cas` is implemented in terms of the set's natural merge semantics.
- `export`/`merge`/`export_all`/`merge_all` replication channel, same shape
  as `lww_register`. Merge = union ∪ union: commutative, associative,
  idempotent.
- Deterministic by construction: tags are `(node_id, counter)` — no wall
  clock, no global RNG. Serialized state is grep-able JSON tagged
  `"crdt": "or_set"`.

**Registration** — `("memory", "or_set")` in `nest_core/plugins.py` builtins
and the `nest.plugins.memory` entry point in
`nest-plugins-reference/pyproject.toml`.

**`tests/test_or_set.py`** — 27 tests:

- Protocol conformance + full read/write/cas/subscribe surface.
- The three CRDT algebraic laws on the pure state (commutativity,
  associativity, idempotence), plus observed-remove correctness.
- **The discriminating test**: the adversarial
  `validate_crdt_convergence` validator **fails against `blackboard` and
  passes against `or_set`** under three different delivery orders.
- **The test that fails without this change**: concurrent writes on two
  replicas — `or_set` preserves both elements; the companion test pins down
  that `lww_register` keeps only one, documenting exactly the gap this
  plugin closes. Registry-wiring tests fail without the `plugins.py` line.
- Determinism: same ops → byte-identical export; merge order does not
  change bytes. Idempotence under duplicated gossip. Malformed-state
  handling via `CrdtStateError`.

## How to run

```bash
pytest packages/nest-plugins-reference/tests/test_or_set.py -v
```

Results on this branch: 27/27 pass; existing `test_lww_register.py`,
`test_plugins.py`, and `test_imports.py` all still pass (74 tests). `ruff
check` and `ruff format --check` clean on all touched files.

## Scope and limits (honest)

- State-based (CvRDT), per the problem's out-of-scope note on CmRDTs.
- Remove tombstones are kept forever; garbage collection is out of scope
  here and called out in the module docstring.
- Reuses the existing generic `validate_crdt_convergence` validator rather
  than duplicating it — it was written capability-based (export/merge) and
  works unchanged for this plugin.

Try it

Open PR on GitHubView diff

Checkout locally

git fetch origin pull/192/head:pr-192
git checkout pr-192