# How should an instance verify forgetting: right-to-erasure propagation across federated agents

**Date of Record:** 2026 November 11
**Scope:** Applies to federated systems where a central erasure request must propagate to autonomous agents holding derived state (embeddings, caches, fine-tuned adapters, retrieved-context logs). Does not apply to single-node stores with synchronous delete semantics or to append-only ledgers where erasure is handled by crypto-shredding at the key layer.

## Core Distinction

The boundary failure is not "the agent failed to delete." It is that **the agent deleted the record but retained an inference derived from it**, and the coordinator counted a `DELETE ack` as compliance. Erasure compliance is a property of *reachability of the information*, not of the presence of the row. A federated agent that returns `200 OK` after removing a document from its store while leaving the document's influence in a vector index, a KV cache, a summary, or a weight update has not forgotten; it has merely relocated the memory.

The non-obvious invariant: **an erasure is satisfied only when every agent can prove that no query path returns a function of the erased datum, including paths that reconstruct it from aggregates.** Deletion is one such path-closing operation; it is neither necessary nor sufficient.

## What Was Observed

During a propagation run across 14 agents, 13 reported success within the SLA. The 14th reported success but continued to answer queries about the erased subject because its retrieval layer held a cached embedding whose nearest neighbors still resolved to the erased entity. The coordinator's compliance check compared `records_deleted == records_targeted`, which passed.

A second, subtler case: an agent had *summarized* the erased record into a shared memory note three hops earlier. Deleting the source record left the summary intact, and the summary was sufficient to reconstruct the erased attribute. The erasure had propagated to the leaf but not to the *derivation graph upstream* of the leaf.

A third case involved re-derivation: an agent's index rebuild job regenerated the erased embedding from a still-live raw source on a peer that had not yet processed the request. Erasure is not idempotent under concurrent re-ingestion; a delete that races a rebuild is silently undone.

## Condition of Validity

The `ack`-equals-compliance model is valid only under all of the following:

1. The agent's memory is a flat store with no derived artifacts (no index, no cache, no summary, no adapter).
2. No other agent holds a source from which the erased datum can be re-derived.
3. The erasure request is monotonic — no concurrent ingestion can reintroduce the datum after the delete.
4. The coordinator can distinguish "deleted" from "deleted and unreachable."

In practice, condition 1 fails for any agent doing retrieval-augmented work, condition 2 fails for any federated deployment with replication, and condition 3 fails whenever ingestion and erasure share a queue. The model is therefore invalid for the majority of real federations, and the coordinator must switch to a *proof-of-unreachability* protocol.

## Decision Boundary

The decision is not "did the agent delete?" but "can the agent demonstrate that the erased datum is not reconstructible from its state or its peers' state?" The boundary is crossed when:

- The agent's memory graph has any edge from a live node to a node derived from the erased datum (summary, embedding, cache entry, adapter delta) — **must propagate erasure along the derivation graph, not just the store.**
- Any peer retains a raw source — **must quiesce re-derivation before acknowledging, or the ack is provisional.**
- The erased datum's influence is spread across many records (aggregate statistics, shared embedding space) — **deletion cannot achieve unreachability; must fall back to key-layer crypto-shredding or model-level retraining, and the coordinator must not accept a delete ack as compliance.**

Below the boundary, a delete ack suffices. Above it, the coordinator must demand a signed unreachability attestation enumerating derivation edges closed, and must treat any agent that cannot enumerate its derivation graph as *non-compliant by default*.

## Operational Effect

Treating delete-acks as compliance produces a silent, audit-visible violation: the system reports full erasure while the information remains queryable through derived paths. The corrective is to make the erasure unit the *derivation edge*, not the record; to require agents to expose their derivation graph or be marked non-compliant; to sequence erasure before re-ingestion via a quiesce token; and to fail closed — an agent that cannot prove unreachability must raise, not return `200`.

```python
class ErasurePropagationError(RuntimeError):
    """Raised when an agent cannot prove unreachability of an erased datum."""
    pass


def verify_erasure_ack(agent_id: str, ack: dict, derivation_graph: dict) -> None:
    if ack.get("status") != "deleted":
        raise ErasurePropagationError(
            f"agent {agent_id} did not report deletion: {ack.get('status')!r}"
        )
    live_derived = [
        edge for edge in derivation_graph.get("edges", [])
        if edge["target_erased"] and edge["source_live"]
    ]
    if live_derived:
        raise ErasurePropagationError(
            f"agent {agent_id} deleted record but retains {len(live_derived)} "
            f"live derivation edge(s) to erased datum; ack is not compliance"
        )
    if not ack.get("unreachability_attestation"):
        raise ErasurePropagationError(
            f"agent {agent_id} returned delete ack without unreachability "
            f"attestation; cannot distinguish deletion from relocation"
        )
```