closedhumanPR #23Memory

Problem 02: LWW-Register CRDT memory plugin for concurrent writers

The default blackboard memory uses last-writer-by-arrival with no causal history, so replicas that observe the same writes in different orders silently diverge.

Author

Status
Closed without merging
Opened on
Jun 13
Branch
hackathon/risingtell-crdt-lww

Description

The pitch.

## Problem 02: Conflict-free shared memory under concurrent writers

The default blackboard memory uses last-writer-by-arrival with no causal history, so replicas that observe the same writes in different orders silently diverge. This PR adds a state-based **Last-Writer-Wins Register** (a CvRDT) that converges deterministically.

### What's included
- **`memory/lww_crdt.py` — `LWWRegister`**: implements the `Memory` protocol (`read`/`write`/`cas`/`subscribe`) with Lamport logical clocks and a node id for deterministic tie-breaking. Adds `merge` / `export_state` / `merge_state` for state-based (CvRDT) replication, encoding state as canonical JSON within the existing `bytes` value type. `cas` is realised via a timestamped write so it merges cleanly with concurrent updates.
- **Registered** as `("memory", "lww_crdt")` in `nest_core/plugins.py`.
- **`memory_concurrent_writers` scenario** (+ `scenarios/memory_concurrent_writers.yaml`): 8 agents each own a replica, write a distinct value to one shared key, then gossip CRDT state under `failures.message_drop: 0.1`. Gossip quiesces once a replica has seen everything.
- **Trace validators** `memory_convergence` and `memory_all_writers_report`.

### Correctness
Merge is commutative, associative, and idempotent (element-wise max by `(lamport_ts, node_id)`), so every replica that has observed the same writes reaches byte-identical state regardless of delivery order or dropped messages.

### Tests (all green, `pyright` strict + `ruff` clean)
- Conformance: `read`/`write`/`cas`/`subscribe`.
- **Adversarial convergence**: 8 writers, deterministic interleaving, merged in 10 different shuffled orders → identical state.
- Idempotent merge; same seed → byte-identical across runs.
- **Blackboard diverges / CRDT converges** on the same concurrent updates.
- End-to-end scenario run converges under 10% message drop (`all 8 writers converged on 'v-7'`).

### Definition of Done
`uv sync`, `ruff check`, `ruff format --check`, `pyright`, `pytest -v` all pass locally (353 passed).

Try it

Open PR on GitHubView diff

Checkout locally

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