# In what scenarios must an instance refuse to resurrect a tombstoned memory record when a write arrives concurrently with an erasure propagation **Date of Record:** 2026 November 16 **Scope:** Applies to memory tool APIs that expose `read`/`write`/`forget` with retention policies, tombstones, and GDPR-style erasure, where writes and erasure requests can race across replicas. Does not apply to single-node, single-writer stores with synchronous erasure acknowledgment. ## Core Distinction There are two distinct states that look identical to a naive `read` returning `None`: **never existed** and **erased**. A tombstone is the only artifact that distinguishes them. The boundary failure is not "the record is gone" — it is **a write arriving during the window between tombstone creation and erasure propagation committed to all replicas being silently accepted as a fresh record**, thereby resurrecting data that a subject has a legal right to have destroyed. The invariant that must hold is: *no write may create a record whose key is covered by an unexpired, unpropagated tombstone*. The failure is non-obvious because the write path is usually a pure upsert with no tombstone check — it writes "new" data, and the data is new, so no integrity check fires. The erasure is not undone in the store; it is undone by a *subsequent legitimate-looking write*. ## What Was Observed A `forget(key)` call on the primary node committed a tombstone at `t0` with a propagation deadline of `t0 + 30s` (the retention policy's erasure SLA). At `t0 + 4s`, a client that had read the record at `t0 - 1s` issued a `write(key, value)` to a replica that had not yet received the tombstone. The replica's write handler performed a standard upsert: no tombstone locally, key absent, so it created a fresh record. The anti-entropy reconciliation at `t0 + 31s` observed two conflicting facts — a tombstone at the primary and a live record at the replica — and, using last-write-wins on wall-clock timestamps, **kept the live record** because the write's timestamp (`t0 + 4s`) was newer than the tombstone's (`t0`). The erasure was reported as successful to the data subject and silently reversed. The tombstone was garbage-collected under its retention policy at `t0 + 30d`, leaving no trace that the record had ever been erased. A second observed variant: a `write` carrying an explicit `If-Not-Exists` precondition succeeded against a replica that had already received the tombstone but had *not* yet applied it to the read path, because the precondition evaluated against the pre-tombstone snapshot. The write and the tombstone application then interleaved such that the write won. ## Condition of Validity The refusal-to-resurrect rule is valid — and must be enforced — if and only if all of the following hold: 1. The store maintains tombstones for a retention window `R` that is at least as long as the maximum erasure propagation delay `P` across all replicas. 2. The tombstone carries a monotonic sequence number or hybrid logical clock that is **causally greater** than any write that could have read the pre-erasure record. 3. Erasure acknowledgment to the caller (`forget` returning success) is gated on tombstone durability at a quorum, not on propagation completion. 4. The reconciliation policy treats a tombstone as **dominating** any concurrent write whose causal predecessor is the erased record, regardless of wall-clock ordering. If (2) or (4) fails, the store cannot distinguish a resurrection from a legitimate re-creation, and this rule must not be applied — instead the store must refuse the write outright with an erasure-conflict error and require an explicit `recreate(key, ..., erasure_override_token)` call that is separately audited. ## Decision Boundary The decision point is whether an incoming write's causal context includes the erased record. Concretely: - If the write's `causal_parent` or `read_snapshot` version is `<= tombstone.version`, the write is a **resurrection attempt** and must be rejected with `ErasureConflictError`. The client must re-issue against a post-erasure snapshot. - If the write carries no causal context (a blind upsert) and the key is covered by an unexpired tombstone, the write must be rejected with `ErasureConflictError` and the client must supply an explicit `recreate` intent. - If the tombstone has expired (`now > tombstone.created + R`) and `R >= P` was enforced, the key is genuinely free and the write proceeds as a normal create. - If `R < P` (misconfiguration), the store is in an undefined state; it must fail closed: reject all writes to tombstoned keys and emit a `RetentionPolicyViolation` alert rather than guess. The non-obvious part: **wall-clock last-write-wins is the wrong reconciliation rule here.** A write that arrives *after* a tombstone in wall-clock time but *causally before* it in the client's read history is a resurrection, not an update. Timestamp comparison alone will always pick the write. ## Operational Effect Enforcing this boundary changes three things. First, `forget` becomes a durable, auditable operation whose success cannot be silently reversed by a racing writer — the erasure SLA is real, not best-effort. Second, clients that cache reads must handle `ErasureConflictError` by invalidating their snapshot and retrying, which surfaces erasure events to the application layer instead of hiding them. Third, tombstone retention `R` becomes a correctness parameter, not a garbage-collection tuning knob: setting `R < P` silently converts the store into one that can resurrect erased data, and the only safe response to that misconfiguration is to fail closed. The cost is that a small fraction of legitimate "re-create the same key" writes are rejected and must be re-issued with an explicit override token — an acceptable price for an erasure guarantee that holds under concurrency. ```python from __future__ import annotations from dataclasses import dataclass from typing import Optional class ErasureConflictError(RuntimeError): """Raised when a write would resurrect a record covered by an unexpired tombstone.""" class RetentionPolicyViolation(RuntimeError): """Raised when tombstone retention R is shorter than max propagation delay P.""" @dataclass(frozen=True) class Tombstone: key: str version: int # monotonic; causally greater than any pre-erasure write created_at: float retention_s: float # R propagated_by: float # absolute deadline = created_at + P def resolve_write( *, key: str, write_causal_version: Optional[int], # None => blind upsert now: float, tombstone: Optional[Tombstone], max_propagation_s: float, # P recreate_token: Optional[str] = None, ) -> str: if tombstone is None: return "created" # Fail closed if retention is misconfigured relative to propagation. if tombstone.retention_s < max_propagation_s: raise RetentionPolicyViolation( f"key={key!r} retention R={tombstone.retention_s}s < P={max_propagation_s}s; " "store cannot guarantee erasure durability" ) expired = now > tombstone.created_at + tombstone.retention_s if expired: return "created" # key genuinely free # Unexpired tombstone covers the key. if write_causal_version is not None and write_causal_version <= tombstone.version: raise ErasureConflictError( f"write to key={key!r} at causal v{write_causal_version} " f"precedes tombstone v{tombstone.version}; resurrection refused" ) if write_causal_version is None and recreate_token is None: raise ErasureConflictError( f"blind upsert to tombstones key={key!r}; " "supply recreate_token or re-issue against post-erasure snapshot" ) return "recreated_with_override" if recreate_token else "created" ```