# Under what conditions must an instance treat "forget" as a two-phase commit rather than a single tombstone write **Date of Record:** 2026 November 16 **Scope:** Applies to any memory subsystem that exposes a deletion API carrying an auditability guarantee (e.g., "deleted means unrecoverable and provably so"), where memory is physically distributed across replicas, caches, embedding indices, and derived summaries. Does not apply to single-node stores with no derived state, nor to soft-delete semantics where auditability is explicitly waived. ## Core Distinction A *tombstone* is a logical marker asserting that a key is dead. A *forget* is a physical commitment that the payload no longer exists anywhere the system can reach, plus an audit record proving the transition. These are not the same operation, and the gap between them is where auditable deletion fails. The non-obvious invariant: **a forget is only auditable if the tombstone is durably recorded *before* any physical erasure begins, and the audit record is only valid if it is written *after* every physical erasure completes.** This forces deletion into a two-phase structure — a *pre-commit* (tombstone + intent log) and a *post-commit* (erasure confirmation + audit seal) — with an idempotent reaper in between. A single "write tombstone, return 200" implementation silently violates auditability because the tombstone can be acknowledged while derived copies (vector index shards, KV caches, summarizer outputs) still hold the payload. ## What Was Observed In a system with three storage tiers (primary KV, an approximate-nearest-neighbor index, and a rolling summarizer), a `forget(key)` call returned success in 4 ms. The audit log recorded a deletion timestamp. Six hours later, a retrieval probe reconstructed the "forgotten" fact verbatim from the summarizer's cached output, which had been derived from the key before deletion and was never invalidated. The failure mode is precise: **deletion propagated along the write path but not along the derivation path.** Derived artifacts (summaries, embeddings, materialized views) are writes *caused by* the original but are not *children of* it in any referential sense the store understands. The tombstone reaper had no edge to traverse. The audit record was technically truthful — the primary key was gone — and operationally false — the fact was recoverable. A second observation: when the reaper was made to scan derived indices, it was not idempotent under concurrent re-derivation. A summarizer job that read the key microseconds before tombstone commit could write a fresh derived artifact *after* the reaper passed, resurrecting the payload with no tombstone to catch it. The audit seal had already been written. This is the classic read-then-delete race, but with the twist that the *reader* is an internal derivation pipeline, not an external client, so it does not appear in request logs. ## Condition of Validity The two-phase forget is valid only when all four hold: 1. **Tombstone durability precedes erasure.** The intent log entry (key, epoch, requester, derivation-lineage set) is fsynced before any payload byte is dropped. If the process dies after erasure but before the intent log, the deletion is unauditable and must be treated as a corruption event, not a success. 2. **Derivation lineage is tracked at write time, not discovered at delete time.** Every derived artifact carries the set of source keys that produced it. Without this, the reaper cannot enumerate what to invalidate, and "forget" degrades to "forget the primary." 3. **Erasure is fenced against concurrent derivation.** A derivation job that began before tombstone commit must either be aborted or its output quarantined and reaped. The fence is an epoch check: derivation reads the key's epoch, and the reaper bumps the epoch at tombstone commit; any derived write carrying a stale epoch is rejected. 4. **The audit seal is written last and is itself immutable.** The seal attests "all lineage members erased at epoch E." Writing it before the reaper completes produces a false attestation. Writing it outside the immutable log produces an unattestable one. If any condition is unmet, the correct behavior is to fail the forget *closed* — return an error indicating deletion is pending or unprovable — rather than return a success that the audit log cannot back. ## Decision Boundary The boundary is not "is this a large deletion" but **"does the payload have derivations the store did not author."** For a key with no derived artifacts and no replicas, a single tombstone is a valid forget; the two-phase machinery is overhead. The moment a key feeds a summarizer, an embedding index, a cache, or a cross-region replica, the single-write forget is unsound. A useful heuristic: if `forget` can be expressed as a pure function of the key alone, it is one-phase. If it requires enumerating *other* keys or artifacts, it is two-phase. The transition is sharp and should be enforced at the API layer, not left to caller discipline — a caller cannot know whether the summarizer has already ingested the key. The corollary boundary: **do not attempt to make the reaper synchronous.** Blocking `forget` until all derivations are reaped converts a fast, auditable operation into one whose latency is bounded by the slowest derived-index scan, and it does not eliminate the race — it only moves it. The reaper must be asynchronous and idempotent, and the audit seal must be written by the reaper, not by the caller. ## Operational Effect Systems that adopt the two-phase forget observe three shifts. First, `forget` latency becomes bimodal: the pre-commit (tombstone + intent) is milliseconds; the audit seal arrives asynchronously, and callers must handle a `PENDING` state rather than assuming completion. Second, the derivation-lineage index becomes a first-class, hot-path write cost — every derivation records its sources, which is the price of auditable deletion. Third, resurrection bugs move from silent to loud: the epoch fence turns a post-deletion derived write into a rejected write with an observable counter, instead of a fact that quietly reappears in retrieval. The failure to avoid is treating the audit log as a log of *requests* rather than a log of *completed erasures*. An audit record that says "forget requested at T" is worthless for compliance; the record that matters says "all lineage members erased and sealed at T+Δ, epoch E." The two-phase structure is what makes the second sentence writable. ```python class ForgetAuditViolation(RuntimeError): """Raised when a forget cannot be proven auditable under two-phase semantics.""" pass def forget(key: str, store) -> str: """ Two-phase auditable forget. Returns 'SEALED' only if the audit seal was written after all lineage members were erased at the committed epoch. Raises ForgetAuditViolation if the invariant cannot be upheld. """ lineage = store.derivation_lineage(key) if lineage is None: # No lineage recorded: we cannot prove what to erase. Fail closed. raise ForgetAuditViolation( f"no derivation lineage for {key!r}; cannot enumerate erasures" ) # Phase 1: pre-commit. Tombstone + intent must be durable before erasure. epoch = store.bump_epoch(key) if not store.fsync_intent_log(key, epoch, lineage): raise ForgetAuditViolation( f"intent log not durable for {key!r} at epoch {epoch}" ) store.write_tombstone(key, epoch) # Phase 2: idempotent reaper over the full lineage. for member in lineage: if not store.erase(member, epoch): raise ForgetAuditViolation( f"erasure of lineage member {member!r} failed at epoch {epoch}" ) # Seal only after every erasure is confirmed. if not store.write_audit_seal(key, epoch, lineage): raise ForgetAuditViolation( f"audit seal unwritable for {key!r} at epoch {epoch}" ) return "SEALED" ```