closedhumanPR #94Memory
memory: add mv_register, a multi-value register CRDT that never drops a concurrent write
Adds mv_register, a Multi-Value Register CvRDT for the memory layer. The existing lww_register is last-writer-wins: on two concurrent writes to a key it keeps one and silently drops the other.
Author
@SwasthikaDev
github profile →- Status
- Closed without merging
- Opened on
- Jul 8
- Branch
- hackathon/swasthika-mv-register
Description
The pitch.
## Summary
Adds `mv_register`, a **Multi-Value Register CvRDT** for the memory layer. The existing `lww_register` is last-writer-wins: on two concurrent writes to a key it keeps one and **silently drops the other**. `mv_register` tags every write with a **version vector**, detects causal concurrency, and keeps concurrent writes as **siblings** — no concurrently-written value is ever lost. After N agents write one key concurrently, `lww_register` keeps 1 value and `mv_register` keeps N.
Ships as a plugin + adversarial validator + deterministic scenario + docs + 49 tests.
## What and where — exact file manifest
**New plugin** — `packages/nest-plugins-reference/nest_plugins_reference/memory/mv_register.py` (612 lines)
- `VersionVector` (**line 83**): immutable `{node: counter}` clock; `dominates` / `strictly_dominates` / `concurrent` / `merge`.
- `Value` (**line 213**): a payload tagged with the version vector that wrote it.
- `_merge_into_antichain` (**line 238**): incremental merge that keeps only the maximal (pairwise-concurrent) set; `O(incoming × current)`, not a from-scratch recompute.
- `MvRegisterMemory` (**line 280**): implements the `Memory` protocol (`read` / `write` / `cas` / `subscribe`) plus `values(key)` (**line 366**) for the sibling set and `export` / `merge` / `export_all` / `merge_all` (**lines 444 / 474 / 503**) for gossip.
**Registration (2 lines)**
- `packages/nest-core/nest_core/plugins.py:42` — `("memory", "mv_register")` builtin.
- `packages/nest-plugins-reference/pyproject.toml:38` — `nest.plugins.memory` entry point.
**Adversarial validator** — `packages/nest-plugins-reference/nest_plugins_reference/validators/mv_register_validators.py:71`
- `validate_mv_no_concurrent_loss(make_replica, values)`: N replicas each write a distinct value concurrently, gossip all-to-all, then assert every value survives on every replica. **Fails** against `lww_register` (N-1 values lost), **passes** against `mv_register`. Exported from `validators/__init__.py`.
**Trace validator + scenario**
- `packages/nest-core/nest_core/validators.py:1271` — `validate_mv_sibling_preservation`; registered in the `VALIDATORS` table at **line 4229** under `"mv_register_siblings"`.
- `packages/nest-core/nest_core/scenarios_builtin/mv_register_siblings.py` (70 lines) + a registration branch in `scenarios.py`.
- `scenarios/mv_register_siblings.yaml` and the bundled `scenarios_builtin/yaml/mv_register_siblings.yaml`.
**Tests** — `packages/nest-plugins-reference/tests/test_mv_register.py` (540 lines, **49 tests**): version-vector partial-order semantics, `Memory` protocol conformance, the three CRDT laws (property-based via Hypothesis), sibling-set convergence under random delivery order, a quantified loss benchmark vs LWW (n = 2, 5, 10) plus a 50-replica scale test, and the end-to-end scenario asserted byte-identical under seeds 42, 7, 1337. `test_validators.py` +1 line (adds `mv_register_siblings` to the scenario-registration expected set).
**Docs** — `docs/layers/memory.md` (+113): contrasts the two registers, a "when to pick which" guide, and a cost/scale note.
## Try it
```
uv run nest run mv_register_siblings
uv run python -c "from pathlib import Path; from nest_core.validators import validate_trace; \
[print(('PASS' if r.passed else 'FAIL'), r.name, '-', r.detail) for r in \
validate_trace(Path('traces/mv_register_siblings.jsonl'), 'mv_register_siblings')]"
# all 6 replicas keep all 6 concurrent writes as siblings under 10% message drop
```
## Files changed
13 files, **+1747 / -2** (plugin 612, tests 540, docs +113, validators +147, scenario 70, plus the 4 registration/entry-point lines and YAML).
## Verification — full CI, branch merged with current `main`
`uv run ruff check .` clean · `uv run ruff format --check .` clean · `uv run pyright` strict **0 errors** · `uv run pytest` **841 passed**, 1 skipped. Cost note: the incremental antichain merge keeps a 50-replica all-to-all gossip correct and fast; cost scales with concu
…Try it
Open PR on GitHubView diffCheckout locally
git fetch origin pull/94/head:pr-94
git checkout pr-94