# What happens when an instance forgets a memory that was never propagated to a replica: the provenance-erasure divergence invariant

**Date of Record:** 2026 November 14

**Scope:** Applies to distributed memory stores exposing read/write/forget APIs with per-record provenance chains and GDPR-style erasure obligations, where writes are replicated asynchronously and forget operations are tracked as first-class tombstones. Does not apply to single-node stores, to stores where erasure is implemented as synchronous quorum deletion, or to append-only logs where "forget" is merely a read-time filter.

## Core Distinction

The critical distinction is between **logical erasure** (the forget API returns success because the primary's provenance chain has been marked erased) and **physical erasure** (every replica, backup, and derived index no longer holds the bytes). A provenance-tracked forget API is designed to make the *logical* transition auditable: it records who requested erasure, when, under what legal basis, and which record IDs were affected. It does **not**, by itself, guarantee that a replica that received a write but not the subsequent forget has any awareness that the record is now subject to erasure.

The non-obvious failure arises at the intersection of three independently reasonable design choices:
1. Writes replicate asynchronously and may be *in flight* when the forget is issued.
2. Forget is represented as a tombstone in the primary's provenance log, not as a mutation of the record's payload.
3. Replicas apply writes in arrival order and only consult tombstones for *future* reads, not retroactively for writes already buffered.

The result: a write that lands on a replica *after* the forget has been acknowledged at the primary can resurrect the erased record on that replica, with a provenance chain that appears locally valid because the replica never saw the tombstone.

## What Was Observed

In a three-replica memory store with a primary and two asynchronous followers, the following sequence was reproduced deterministically under a 400 ms replication lag:

1. Client issues `write(mem_id="m1", payload=P, provenance=chain_A)`. Primary acknowledges. Replication to follower-2 is queued.
2. Client issues `forget(mem_id="m1", basis="gdpr_art17", requestor="dsar-7741")`. Primary marks `m1` erased in its provenance log, returns `{status: "erased", tombstone_id: T1}`. The forget tombstone is enqueued to both followers.
3. Follower-1, which was ahead, applies `T1` then the buffered write — correctly discards the write.
4. Follower-2's replication stream interleaves such that the *write* is applied first (arriving from a retry after a transient network reset), then `T1` is applied. Follower-2's tombstone application is a no-op on a record it now believes was written *after* the tombstone's logical timestamp, because the write's provenance chain carries a client-side clock that is ahead of the tombstone's primary-assigned sequence.
5. A read routed to follower-2 returns `P` with a *valid* provenance chain (`chain_A` plus a locally synthesized "post-erasure" marker). The record is logically resurrected.

The provenance chain on follower-2 is internally consistent: it has a write with a chain, and it has a tombstone with a *lower* logical timestamp than the write. No invariant in the replica's local validator fires. The divergence is only detectable by cross-referencing the primary's tombstone sequence against the replica's applied-write sequence — a check that the read path does not perform because it would require a round trip.

## Condition of Validity

The invariant **"a forget acknowledged at the primary implies the record is unreadable from all replicas"** holds only under one of:

- **Synchronous quorum erase:** the forget is not acknowledged until a quorum of replicas has applied the tombstone *and* drained any in-flight writes for that ID. This is the safe default and the only condition under which the forget response can be treated as a compliance guarantee.
- **Monotonic sequence authority:** writes and tombstones share a single primary-assigned sequence number, and replicas reject any write whose sequence is lower than an already-applied tombstone for the same ID. This requires the client-side provenance clock to be *ignored* for ordering and treated as advisory metadata only.
- **Read-time reconciliation:** every read of a record marked erased-at-primary is forced to consult the primary tombstone index before returning payload. This trades latency for correctness and is only viable for low-QPS erasure-sensitive reads.

If none of these hold, the forget API's success response is a statement about the *primary's provenance log*, not about the system's memory. The two are not the same, and the gap is exactly the replication lag window multiplied by the probability of an in-flight write for the forgotten ID.

## Decision Boundary

The boundary is crossed when **a write for `mem_id` X is enqueued to a replica after the forget tombstone for X has been enqueued to that same replica, but the write's client-provenance timestamp exceeds the tombstone's primary sequence**. At that point:

- The replica's local validator sees a "newer" write and a "stale" tombstone.
- The write is applied; the tombstone is recorded but marked superseded.
- The record is readable again on that replica.

The correct decision at the API layer is to **never let a write and a forget for the same ID be concurrently in flight to the same replica**. This is enforceable by having the forget path perform a *drain barrier*: before enqueuing the tombstone, the primary waits until all pending writes for that ID have been acknowledged by every replica in the replication set, or until a bounded timeout after which the replica is marked degraded and excluded from reads for that ID. The drain barrier is cheap (it is a per-ID counter, not a global fence) and it closes the window without requiring synchronous quorum on the forget itself.

A secondary decision boundary: **provenance timestamps must never be used for ordering against tombstones.** They are audit metadata. Ordering must be by primary-assigned sequence. Mixing the two is the root cause of the resurrection above.

## Operational Effect

The observable effect is a **silent erasure miss**: the DSAR (data subject access request) is recorded as fulfilled, the provenance log shows a valid tombstone, the compliance dashboard is green, and yet the payload is retrievable from at least one replica for an unbounded period (until compaction, backup rotation, or a manual audit). The failure is silent because every component's local invariant holds; only the *cross-component* invariant — "forget at primary implies unreadable everywhere" — is violated, and no component owns that invariant by default.

The remediation that worked in practice:

1. Add a per-ID drain barrier to the forget path (bounded, with degraded-replica exclusion on timeout).
2. Reject replica-side writes whose ID has an applied tombstone with a *lower* primary sequence, regardless of client provenance timestamp.
3. Emit a divergence metric: count of IDs where primary tombstone sequence < replica's highest applied write sequence. Alert on any nonzero value.
4. On read of an erased-at-primary ID, force a tombstone check against the primary index (or a cached tombstone bloom filter refreshed at a bounded staleness).

The following Python sketch encodes the validator that must run on every replica write application. It is the check whose absence produced the resurrection; its presence converts a silent erasure miss into a loud, attributable failure.

```python
class ErasureDivergenceError(RuntimeError):
    """Raised when a replica is about to apply a write that would resurrect
    a record already subject to an applied forget tombstone."""
    pass


class TombstoneIndex:
    def __init__(self):
        # mem_id -> highest primary sequence at which a forget was applied
        self._applied = {}

    def apply_tombstone(self, mem_id: str, primary_seq: int) -> None:
        prev = self._applied.get(mem_id)
        if prev is None or primary_seq > prev:
            self._applied[mem_id] = primary_seq

    def tombstone_seq(self, mem_id: str):
        return self._applied.get(mem_id)


class ReplicaWriteValidator:
    def __init__(self, tombstones: TombstoneIndex):
        self.tombstones = tombstones

    def validate_and_apply(self, mem_id: str, write_primary_seq: int,
                           client_provenance_ts: int, payload: bytes) -> None:
        # Ordering authority is the primary sequence, NOT the client provenance
        # timestamp. Client provenance is advisory audit metadata only.
        tomb_seq = self.tombstones.tombstone_seq(mem_id)
        if tomb_seq is not None and write_primary_seq < tomb_seq:
            raise ErasureDivergenceError(
                f"write for {mem_id!r} at primary_seq={write_primary_seq} "
                f"is older than applied tombstone at primary_seq={tomb_seq}; "
                f"applying it would resurrect an erased record "
                f"(client_provenance_ts={client_provenance_ts} is ignored for ordering)"
            )
        if tomb_seq is not None and write_primary_seq == tomb_seq:
            # Same sequence cannot be both a write and a forget; this indicates
            # a primary-side sequencing bug and must fail closed.
            raise ErasureDivergenceError(
                f"write and tombstone share primary_seq={write_primary_seq} "
                f"for {mem_id!r}; refusing to apply"
            )
        # Safe to apply: write is strictly newer than any applied tombstone.
        # (Payload application elided; the invariant check above is the point.)
        _ = payload


def forget_with_drain_barrier(primary, mem_id: str, basis: str,
                              requestor: str, replicas, timeout_ms: int = 2000):
    """Forget path: drain in-flight writes for mem_id before enqueuing the
    tombstone, so no replica can observe a write enqueued after the tombstone
    but carrying a higher client provenance timestamp."""
    pending = primary.pending_writes_for(mem_id)
    if pending:
        drained = primary.wait_for_acks(pending, timeout_ms=timeout_ms)
        if not drained:
            degraded = primary.replicas_with_pending(pending)
            for r in degraded:
                r.mark_degraded_for(mem_id)
            # Fail closed on the forget: do not acknowledge erasure while a
            # replica could still resurrect the record.
            raise ErasureDivergenceError(
                f"cannot guarantee erasure of {mem_id!r}: replicas {degraded} "
                f"still hold in-flight writes after {timeout_ms}ms; "
                f"forget NOT acknowledged (basis={basis}, requestor={requestor})"
            )
    return primary.enqueue_tombstone(mem_id, basis=basis, requestor=requestor)
```