in reviewhumanPR #137Memory
feat(memory): implement OR-Set CvRDT memory plugin with tick clock sy…
This PR implements a robust, API-compliant state-based OR-Set (Observed-Remove Set) memory plugin to resolve Problem 02 (memory-crdt-lww).
Author
@virajsh4h
github profile →- Status
- In review
- Opened on
- Jul 9
- Branch
- hackathon/virajsh4h-or-set-memory
Description
The pitch.
## Hackathon Problem 02: API-Compliant OR-Set CvRDT Memory Layer This PR implements a robust, API-compliant state-based OR-Set (Observed-Remove Set) memory plugin to resolve **Problem 02 (memory-crdt-lww)**. It provides a strict, deterministic CvRDT (Shapiro et al., SSS 2011) that fits transparently into the Nanda Town `Memory` protocol. ### 🛠️ Architecture & Core Enhancements 1. **API Protocol Compliance**: - **`read()` & `subscribe()`**: Yields the raw winning user payload, matching the exact behavior of `LwwRegisterMemory` and avoiding any leaks of internal CRDT state envelopes to subscribers. - **`cas()`**: Operates directly on raw user payloads (not JSON state strings), ensuring standard clients can linearize operations locally. - **Anti-entropy `merge()` Optimization**: Evaluates state transitions and only triggers subscriber notifications when the local state actually advances, completely eliminating infinite broadcast loops (gossip storms). 2. **Node Priority Inversion Guard**: - Rather than sorting tags lexicographically as strings (where `"writer-1:0"` would dominate `"writer-0:100"`), tags are parsed and sorted primarily by the `tick` integer, using the `node_id` strictly as a secondary tie-breaker. 3. **Volatile Counter Sync**: - To prevent duplicate tag generation and silent write tombstones on node restarts or replica initialization, the replica's local clock `tick` is dynamically updated during `merge()` to `max(local_tick, max_incoming_tick + 1)`. 4. **Defensive Schema Checks**: - Implements strict validation on incoming merge payloads to filter out malformed schemas (ensuring `elements` is a dictionary and `tombstones` is a list) to prevent runtime denial-of-service (DoS) crashes. --- ### 🧪 Test Rigor & Validation - **Hypothesis Property Tests**: Verifies commutative, associative, and idempotent convergence properties over randomized sequences of writes and removes. - **Blackboard Divergence Test**: Confirms that our adversarial trace validator (`validate_or_set_convergence`) successfully rejects non-CRDT structures (like blackboard). - **Edge-Case Coverage**: Included regression tests specifically verifying: - Lexicographical node ID priority bypass. - Active tick synchronization upon merge. - Defensive type checks for CAS and merges. --- ### ✅ Definition of Done - [x] `uv run ruff check .` passes (0 errors) - [x] `uv run ruff format --check .` passes - [x] `uv run pyright` passes (100% strict type safety) - [x] `uv run pytest -v` passes (962 tests passed) - [x] `nanda run scenarios/memory_or_set.yaml` passes (Validated trace output) ### How to Run Locally ```bash nanda run scenarios/memory_or_set.yaml
Try it
Open PR on GitHubView diffCheckout locally
git fetch origin pull/137/head:pr-137
git checkout pr-137