# When must an instance forget before it can be told it has forgotten: the retention-clock vs. deletion-witness inversion in memory tool APIs **Date of Record:** 2026 November 18 **Scope:** Applies to memory tool APIs that expose `read`/`write`/`forget` verbs with (a) a retention policy expressed as a wall-clock or logical-clock TTL and (b) a verifiable-deletion contract returning a tombstone or deletion witness. Does not apply to append-only stores with no deletion surface, nor to stores whose deletion is a pure physical unlink with no retention metadata. ## Core Distinction Two clocks govern a `forget` call: the **retention clock** (when the policy says the record *may* be purged) and the **witness clock** (when the store can *prove* the record is gone). The non-obvious invariant is that these are not ordered by construction. A store can emit a deletion witness while the retention clock still considers the record live, and it can honor the retention clock while being unable to produce a witness. The boundary failure occurs when a caller treats the witness as authoritative for retention *or* treats retention expiry as authoritative for deletion. Neither implies the other. The subtle case — the one that produces silent corruption — is the **inversion**: a `forget` issued *before* retention expiry returns a witness, the caller records "deleted," but a concurrent or later `read` served from a replica whose retention clock has not yet advanced returns the record anyway. The instance was told it had forgotten; it had not. ## What Was Observed In a replicated memory tool with per-shard retention TTLs and a tombstone-based witness, the following sequence reproduced deterministically under clock skew of ≥ TTL/2 between the writer shard and a read replica: 1. `write(k, v)` at logical time `t0` on shard A; retention expiry `t0 + TTL` recorded in A's metadata. 2. `forget(k)` at `t0 + ε` on shard A. A emits witness `W = (k, tombstone_epoch, hash(v))` and marks the tombstone *pending* until retention expiry, because A's policy forbids physical purge before `t0 + TTL`. 3. Caller persists `W` as proof of deletion. 4. `read(k)` routed to replica B, whose retention clock lags. B has not seen the tombstone (replication lag) and its local retention TTL has not expired, so B returns `v`. 5. Caller observes a successful read of a record it holds a witness for. The witness is *valid* (A will purge at expiry) and the read is *valid* (B has not expired), but the pair is contradictory to any consumer. The failure is not a bug in `forget` or in `read` in isolation. It is a boundary condition of the *contract*: the witness attests to intent-to-delete, not to deletion-now; the retention clock attests to may-delete, not to must-delete. A consumer that collapses the two into one boolean (`deleted = witness_present`) will read deleted data. ## Condition of Validity A deletion witness `W` is a sound proof that a `read(k)` will never return `v` **only if** all of the following hold at the moment of the read: - `W.tombstone_epoch` ≥ the epoch of every replica reachable by the read path (i.e., tombstone replication has converged, not merely been issued). - The read path consults the tombstone set *before* the retention-expiry check, so a live-but-tombstoned record is masked regardless of TTL. - The retention clock on every replica is monotonic and ≥ the clock used at `forget` time; otherwise a replica can "un-expire" relative to the witness. If any of these fail, `W` is a *retention-scoped* witness: it promises deletion at `max(retention_expiry, tombstone_convergence)`, not at issue time. The caller must treat the deletion as **scheduled**, not **complete**, until convergence is independently observed (e.g., a `read` on every replica returns the tombstone, or a convergence token is returned alongside `W`). ## Decision Boundary The operational fork is precise: - **If the consumer requires read-your-deletes (RYD) semantics** (e.g., a right-to-be-forgotten compliance check that must fail closed), the instance must *not* treat an issued witness as deletion. It must either (a) block `read` on `k` locally from `forget`-issue time, or (b) require a convergence token and refuse to report "deleted" until every replica has acknowledged the tombstone epoch. - **If the consumer requires only eventual deletion** (e.g., cache invalidation, best-effort scrubbing), an issued witness is sufficient, but the consumer must never assert "not present" based on it — only "will not be served after convergence." The non-obvious rule: **an instance must forget locally (mask reads) before it can be told it has forgotten (accept the witness as complete).** The mask is the instance's own responsibility; the witness is the store's. Conflating them is the inversion. ## Operational Effect Downstream, this manifests as: compliance audits that pass on witness presence while data is still readable on lagging replicas (a false-negative for deletion); cache layers that trust the witness and re-populate from a replica that has not converged (resurrection); and `read`-after-`forget` tests that pass on the writer shard and fail intermittently on read replicas, producing flaky "deletion is broken" reports that are actually contract misreads. The correct instrumentation is to assert the *conjunction* — witness present AND tombstone epoch ≥ max replica epoch AND local mask active — before any code path reports a record as gone. ```python import time from dataclasses import dataclass, field class DeletionWitnessInversion(RuntimeError): """Raised when a deletion witness is treated as complete while a reachable replica can still serve the record (retention/witness inversion).""" pass @dataclass class Witness: key: str tombstone_epoch: int issued_at: float retention_expiry: float @dataclass class Replica: name: str epoch: int retention_clock: float store: dict = field(default_factory=dict) def can_serve(self, key: str, now: float) -> bool: # A replica serves if it has not seen the tombstone epoch AND its # retention clock has not passed expiry for the record. return key in self.store and self.retention_clock < now class MemoryTool: def __init__(self, ttl: float): self.ttl = ttl self.replicas = [Replica("A", 0, 0.0), Replica("B", 0, 0.0)] self.witnesses: dict[str, Witness] = {} self.local_mask: set[str] = set() def write(self, key: str, value: str, now: float) -> None: for r in self.replicas: r.store[key] = value r.retention_clock = max(r.retention_clock, now) def forget(self, key: str, now: float) -> Witness: epoch = max(r.epoch for r in self.replicas) + 1 w = Witness(key, epoch, now, now + self.ttl) self.witnesses[key] = w # Issue witness; tombstone is *pending* until convergence. self.local_mask.add(key) # instance masks reads before claiming deletion return w def read(self, key: str, replica: str, now: float) -> str | None: r = next(x for x in self.replicas if x.name == replica) w = self.witnesses.get(key) if w is not None and r.epoch >= w.tombstone_epoch: return None # tombstone converged; masked regardless of TTL if key in self.local_mask and r.name == "A": return None if r.can_serve(key, now): return r.store[key] return None def assert_deleted(self, key: str, now: float) -> None: w = self.witnesses.get(key) if w is None: raise DeletionWitnessInversion(f"no witness for {key!r}") max_epoch = max(r.epoch for r in self.replicas) if w.tombstone_epoch > max_epoch: raise DeletionWitnessInversion( f"witness for {key!r} issued at epoch {w.tombstone_epoch} " f"but max replica epoch is {max_epoch}: deletion is scheduled, " f"not complete" ) for r in self.replicas: if r.can_serve(key, now): raise DeletionWitnessInversion( f"replica {r.name!r} can still serve {key!r} at {now}: " f"retention clock {r.retention_clock} < now" ) if key not in self.local_mask: raise DeletionWitnessInversion(f"local mask absent for {key!r}") if __name__ == "__main__": tool = MemoryTool(ttl=10.0) tool.write("k", "v", now=0.0) w = tool.forget("k", now=1.0) # Replica B has not converged; claiming deletion now is the inversion. try: tool.assert_deleted("k", now=2.0) except DeletionWitnessInversion as e: print("caught inversion:", e) # Simulate convergence, then assert is sound. for r in tool.replicas: r.epoch = w.tombstone_epoch r.retention_clock = 20.0 tool.assert_deleted("k", now=21.0) print("deletion verified after convergence") ```