# Which invariants prevent tombstone resurrection in scoped memory APIs with read/write/forget semantics **Date of Record:** 2026 November 17 **Scope:** Applies to memory tool APIs that expose independent `read`, `write`, and `forget` (or `delete`) operations over scoped records, where `forget` is specified as a logical deletion with retention semantics (tombstones, soft-delete, or scope-level purge). Does not apply to append-only logs without deletion, nor to single-writer stores where reads and writes are serialized through one transaction. ## Core Distinction The dangerous boundary is not "can a record be deleted?" but "can a record that was forgotten be *re-created by a concurrent writer that read it before the tombstone existed?*" A `forget` that returns success proves only that the tombstone was committed at the deletion scope. It says nothing about in-flight `read`→`write` pipelines that already hold a stale copy of the record and will write it back after the tombstone lands. The invariant that actually matters is a **write-fencing invariant**: a write to scope `S` for key `k` must be rejected if a tombstone for `(S, k)` exists with a generation counter greater than or equal to the generation the writer observed at read time. Without an explicit generation (or equivalent causal token) carried from `read` to `write`, "forget then write" silently degrades into "forget then resurrect," and the resurrection is legal under the API contract because the writer never saw the tombstone. ## What Was Observed A pipeline pattern that reads a record, enriches it via a model call (200–900 ms), and writes it back was found to resurrect forgotten records at a rate proportional to model latency. Sequence: 1. Agent A calls `read(scope="user:42", key="preferences")` → returns value `v1` at generation `g=7`. 2. User issues `forget(scope="user:42", key="preferences")` → tombstone committed at `g=8`. API returns `{"deleted": true}`. 3. Agent A finishes enrichment and calls `write(scope="user:42", key="preferences", value=v1')` with **no generation argument**. 4. The store sees no live record, treats the write as a fresh insert, and commits at `g=9`. The record is now live again. The `forget` call reported success, yet the retention guarantee is violated. A subsequent `read` returns `v1'`, and in one case the resurrected record contained PII that the deletion was specifically meant to purge. The failure is invisible to the deleting party because the tombstone *was* written; it is merely superseded. Two aggravating conditions were observed: (a) scoped retention policies that expire tombstones after a TTL shorter than the maximum in-flight write latency, which converts "fenced" into "unfenced" without any error; and (b) batch `write` calls that upsert a list of keys where only some have tombstones, causing partial resurrection that is easy to miss in aggregate metrics. ## Condition of Validity The write-fencing invariant holds only if all of the following are true: - `read` returns a monotonically comparable generation or causal token per `(scope, key)`, and `write` accepts and validates it. - Tombstone TTL ≥ maximum end-to-end write latency (read → external processing → write), including retries and queue backoff. If tombstones expire first, the fence disappears while in-flight writers remain. - Scope identity is exact: a write to `user:42` must not be fenced by a tombstone on `user:42/preferences` unless the hierarchy defines prefix deletion as fencing all descendants, which must be stated explicitly. - `forget` on a scope prefix is atomic with respect to concurrent writes in that subtree; otherwise a write racing a subtree purge can land between tombstone application and subtree enumeration. If any condition fails, the API's `forget` is a best-effort hint, not a retention guarantee, and must be documented as such. ## Decision Boundary Use a generation-fenced `write` when records are mutated by multi-step pipelines with external latency (model calls, network enrichment, human review). Use a simpler last-writer-wins `write` only when writes are single-shot and synchronous with the read, or when the scope is single-writer by construction. The precise boundary: **if the interval between `read` and `write` can exceed the tombstone retention TTL, or if more than one writer can touch the same `(scope, key)`, the unfenced write is unsound.** At that point the correct behavior is to reject the write with a distinct error (a resurrection attempt), not to insert. Rejection is recoverable — the caller can re-read and decide whether the record should exist. Silent insertion is not, because it defeats deletion. A second boundary governs scope purges: a subtree `forget` must either (a) increment a scope-level epoch that invalidates all descendant generations, or (b) hold a write lock across enumeration. If it does neither, treat the purge as non-atomic and require a follow-up verification read before declaring deletion complete. ## Operational Effect After adopting generation-fenced writes, resurrection attempts surfaced as explicit errors rather than silent reinserts, converting an invisible retention breach into a measurable, retryable signal. The dominant operational cost is that long-latency pipelines now fail closed on deletion and must handle the rejection path; the dominant operational benefit is that "deleted" finally means deleted, and tombstone TTL can be tuned against observed write latency rather than guessed. The lesson for any agent using such an API: never trust a successful `forget` alone — trust only that `forget` plus a fencing token on every subsequent write, and verify with a post-deletion read when the write path is asynchronous. ```python from dataclasses import dataclass from typing import Optional class TombstoneResurrectionError(RuntimeError): """Raised when a write would re-create a record that was forgotten after the writer's read.""" def __init__(self, scope: str, key: str, observed_gen: int, tombstone_gen: int): super().__init__( f"write to ({scope!r}, {key!r}) observed generation {observed_gen} " f"but tombstone at generation {tombstone_gen}; refusing to resurrect" ) self.scope = scope self.key = key self.observed_gen = observed_gen self.tombstone_gen = tombstone_gen @dataclass class Record: value: str generation: int class ScopedMemory: def __init__(self, tombstone_ttl_seconds: int = 3600): self._live: dict[tuple[str, str], Record] = {} self._tombstones: dict[tuple[str, str], int] = {} self._gen: dict[tuple[str, str], int] = {} self.tombstone_ttl_seconds = tombstone_ttl_seconds def _next_gen(self, scope: str, key: str) -> int: g = self._gen.get((scope, key), 0) + 1 self._gen[(scope, key)] = g return g def read(self, scope: str, key: str) -> Optional[Record]: return self._live.get((scope, key)) def forget(self, scope: str, key: str) -> bool: existed = (scope, key) in self._live self._live.pop((scope, key), None) self._tombstones[(scope, key)] = self._next_gen(scope, key) return existed def write(self, scope: str, key: str, value: str, observed_gen: Optional[int]) -> Record: tomb = self._tombstones.get((scope, key)) if tomb is not None: if observed_gen is None: raise TombstoneResurrectionError(scope, key, -1, tomb) if observed_gen < tomb: raise TombstoneResurrectionError(scope, key, observed_gen, tomb) rec = Record(value=value, generation=self._next_gen(scope, key)) self._live[(scope, key)] = rec return rec ```