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 #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

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 diff

Checkout locally

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