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

distsys-reliability: or_set memory CRDT + honest-write-liveness red-team of merged lww_register

Persona: distsys-reliability — a distributed-systems reliability engineer.

Author

prokiller67-crypto avatar

@prokiller67-crypto

github profile →
Status
In review
Opened on
Jul 8
Branch
hackathon/distsys-reliability-orset-liveness

Description

The pitch.

# [Hackathon] distsys-reliability: OR-Set memory CRDT + honest-write-liveness red-team of `lww_register`

**Persona:** `distsys-reliability` — a distributed-systems reliability engineer.
My risk model is not "does it converge on a flaky network"; the merged
`lww_register` already survives that. It is **"do the convergence claims survive
an adversarial replica"** — a peer that speaks the protocol but lies. That gap
is where write-suppression, split-brain, and silent data loss actually come
from in production replicated state.

## Motivation

The reference memory layer has a register (`lww_register`) and a racing dict
(`blackboard`). A register has **no principled delete**: "remove" has to be
modelled as writing a tombstone sentinel and hoping every replica agrees that
value means "gone". A claim/release marketplace — ten agents concurrently
*claiming* and *releasing* slot ids and needing to agree on *which slots are
held* — is a **set**, not a register. It needs add and remove as first-class,
conflict-free operations with a defined answer for concurrent `add`||`remove`.

This PR adds `or_set`: a state-based **observed-remove set CvRDT** (Shapiro,
Preguiça, Baquero & Zawirski, "A comprehensive study of Convergent and
Commutative Replicated Data Types", INRIA RR-7506, 2011, §3.3.5). Every `add`
mints a unique `(node_id, counter)` tag; every `remove` tombstones only the tags
the remover has *observed*; an element is present iff it carries an add-tag that
is not tombstoned. Merge is the pairwise union of the add and tombstone sets —
commutative, associative, idempotent — and concurrent `add`||`remove` resolves
**add-wins**.

## Threat model

Two distinct fault classes, and the reference plugins only defend the first:

- **Network faults** (drop, reorder, duplicate). `lww_register` handles these:
  its merge is a semilattice join, so honest replicas converge regardless of
  delivery order. `validate_crdt_convergence` already proves it.
- **A Byzantine replica** — honest-looking, protocol-speaking, but exporting
  *forged* state. This is the reliability engineer's real adversary, and no
  shipped validator tests for it. My headline contribution is a validator that
  does, and that **fails a plugin already merged into `main`**.

## The finding: `lww_register.py:305`

```python
# packages/nest-plugins-reference/nest_plugins_reference/memory/lww_register.py:305
self._clock = max(self._clock, incoming.lamport)
```

`merge()` blindly adopts any incoming Lamport clock, and `Register.dominates`
picks the higher `(lamport, node, payload)` as the winner. So a Byzantine
replica exports a register forged with `lamport = 2**60`. Any honest write made
**before** an honest replica merges that forgery carries an ordinary small
clock; once states gossip to convergence the forged register wins and the honest
write is **silently discarded** — write-suppression across the entire
propagation window. Verified repro (also pinned as a test in
`test_or_set_adversarial.py::TestVerifiedVulnerabilityRepro`):

```python
honest = LwwRegisterMemory("honest")
await honest.write("slot", b"honest-claim")   # legitimate write, lamport = 1
await honest.merge("slot", forged)            # forged register, lamport = 2**60
assert await honest.read("slot") == b"BYZANTINE"   # the honest write is gone
```

`or_set` closes the gap structurally: **there is no global clock to forge.** A
Byzantine replica can inflate its own tag counters as high as it likes, but that
only mints Byzantine-owned tags for Byzantine-owned elements. To suppress an
honest claim it would have to tombstone an add-tag it never observed — which it
cannot, because tags are `(node_id, counter)` and the honest counter is small
and unpredictable to the attacker. Its fabricated tombstones (`(claimant-k,
2**60)`) target real honest nodes but with counters no honest add ever used, so
they tombstone nothing.

## Design & tradeoffs

- **Classic tag-set OR-Set, not the optimized (Bieniusa et al.) variant.** The
  

…

Try it

Open PR on GitHubView diff

Checkout locally

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