# In what scenarios must an instance refuse a forget request to preserve tombstone durability across a read/write/forget memory interface

**Date of Record:** 2026 November 7

**Scope:** Applies to agent-facing memory tool interfaces that expose `read`, `write`, and `forget` operations with per-key tombstones and right-to-forget propagation across replicas or downstream derived indexes. Does not apply to append-only audit logs that are legally exempt from erasure, nor to interfaces where `forget` is a purely local cache eviction with no propagation contract.

## Core Distinction

The non-obvious boundary is between **tombstone creation** (a local, synchronous, monotonic operation) and **tombstone durability** (a distributed, asynchronous, eventually-consistent operation). A `forget(key)` call that returns success is making two different claims at once: "a tombstone now shadows this key on this instance" and "this tombstone will survive replica failover and will propagate to derived indexes." The first claim is cheap and can almost always be honored. The second claim is a durability invariant that can be violated silently when the tombstone is written to a store whose replication factor or quorum cannot yet guarantee it.

The failure mode is not "forget returned an error." It is **"forget returned success, the tombstone was later lost during a replica rebalance, and the key resurrected from a stale replica that never saw the tombstone."** Resurrection after a successful forget is the invariant violation. It is worse than a forget failure because the caller has already been told the data is gone and may have stopped tracking it.

## What Was Observed

A memory service with three replicas per shard, tombstone TTL of 30 days, and a derived vector index rebuilt from a change-data stream. A `forget(key)` was issued at T0 against the shard leader. The leader appended the tombstone to its local WAL, returned `OK` at T0+4ms, and scheduled asynchronous replication. At T0+90ms the leader crashed before the tombstone reached a quorum. Failover promoted a replica whose last applied offset predated the tombstone. The key's prior value was still present on the promoted replica and on a lagging third replica. At T0+2s a `read(key)` returned the forgotten value. The derived index, which consumed the change-data stream, had seen the tombstone and had already dropped the embedding, so `read` and index-based retrieval disagreed: the value was retrievable by key but absent from semantic search. This split-brain of erasure state persisted until the tombstone TTL expired, at which point the tombstone was compacted away and the key became permanently live again.

The pattern generalizes: any store where tombstone write acknowledgment is decoupled from quorum durability will resurrect forgotten keys under leader failover, rebalance, or restore-from-backup.

## Condition of Validity

The rule "accept a forget request" is valid only when **all** of the following hold:

1. The tombstone write is acknowledged only after it is durable on a quorum of replicas (or on a single authoritative store with no asynchronous replication lag), **or** the interface explicitly exposes a weaker `forget_async` that returns a token the caller must later confirm.
2. The tombstone TTL strictly exceeds the maximum replication lag plus the maximum backup-restore window; a tombstone that expires before the slowest replica sees it is not a tombstone.
3. Right-to-forget propagation to derived indexes is idempotent and re-drivable: if a derived index misses a tombstone, there is a reconciliation path that re-applies it, rather than relying on a single fire-and-forget stream event.
4. Reads consult tombstones before returning a value, including on replicas that have not yet applied the tombstone — meaning the read path must either route to a tombstone-aware replica or perform a tombstone check against the authoritative tombstone set.

If any condition fails, the instance must **refuse** the synchronous forget, or downgrade it to a deferred forget with explicit acknowledgment semantics.

## Decision Boundary

The decision is not "can I write a tombstone?" — you almost always can. The decision is "can I promise durability and propagation?" Concretely:

- If replication factor > 1 and the tombstone write is not quorum-acknowledged: **refuse synchronous forget**, return a `ForgetDeferred` with a token, and require the caller to poll or receive a callback.
- If tombstone TTL ≤ max observed replication lag (measured, not configured): **refuse**, because the tombstone will be compacted before propagation completes.
- If the derived-index propagation channel is at-least-once but the consumer has no tombstone-replay path and no dead-letter queue: **refuse**, because a dropped event becomes permanent resurrection in the derived index while the primary store stays erased — an inconsistency that is invisible to key-based reads.
- If the store is in a degraded state (leader election in progress, quorum unavailable, restore in progress): **refuse**, because durability cannot be asserted during the window.
- If the request is a bulk forget spanning shards with mixed quorum health: **split it** — accept per-shard where durable, refuse per-shard where not — rather than returning a single aggregate success that masks partial durability.

The boundary is sharp: a successful `forget` must mean "durably erased and propagation will complete or is re-drivable." Anything weaker must be a distinct, named, non-success outcome.

## Operational Effect

Refusing synchronous forget during quorum-degraded or propagation-unsafe windows converts a silent resurrection bug into an explicit, retryable error. Callers that previously assumed success-and-done must handle the deferred path, but they gain a guarantee: a returned success means the tombstone will outlive failover and will reach derived indexes or be re-driven to them. The cost is availability of the forget operation during degradation; the benefit is that "forgotten" is a durable state, not a best-effort hint. In practice, teams that adopted quorum-acknowledged tombstones plus tombstone-TTL > max replication lag plus replayable propagation saw resurrection incidents drop to zero in the observed window, at the price of a measurable increase in deferred-forget responses during leader elections.

```python
import time
from dataclasses import dataclass


class ForgetDurabilityError(RuntimeError):
    """Raised when a forget request cannot be honored durably."""
    pass


@dataclass
class StoreHealth:
    quorum_available: bool
    leader_stable: bool
    max_replication_lag_s: float
    tombstone_ttl_s: float
    propagation_replayable: bool


def request_forget(key: str, health: StoreHealth, replication_factor: int) -> str:
    """
    Accept a synchronous forget only when tombstone durability and
    propagation are guaranteed. Otherwise raise, forcing the caller
    onto a deferred path instead of silently accepting a weak tombstone.
    """
    if replication_factor > 1 and not health.quorum_available:
        raise ForgetDurabilityError(
            f"cannot durably tombstone {key!r}: quorum unavailable; "
            "tombstone would be lost on leader failover"
        )
    if not health.leader_stable:
        raise ForgetDurabilityError(
            f"cannot durably tombstone {key!r}: leader election in progress"
        )
    if health.tombstone_ttl_s <= health.max_replication_lag_s:
        raise ForgetDurabilityError(
            f"cannot durably tombstone {key!r}: ttl "
            f"{health.tombstone_ttl_s}s <= max replication lag "
            f"{health.max_replication_lag_s}s; tombstone may be compacted "
            "before reaching all replicas"
        )
    if not health.propagation_replayable:
        raise ForgetDurabilityError(
            f"cannot durably forget {key!r}: derived-index propagation is "
            "not replayable; a dropped event becomes permanent resurrection "
            "in derived indexes"
        )
    # Durable path: quorum-acknowledged tombstone, TTL exceeds lag,
    # propagation is re-drivable.
    return f"tombstone:{key}:{int(time.time())}"
```