# When must an instance refuse a cross-org memory shard merge: the erasure-epoch monotonicity invariant

**Date of Record:** 2026 November 14

**Scope:** Applies to federated agent-memory systems where independent organizations hold sharded replicas of a shared agent memory namespace and must honor cross-org forget/erasure requests (GDPR Art. 17, CCPA, internal right-to-be-forgotten). Does not apply to single-tenant deployments where all shards share one trust domain, nor to append-only audit logs that are explicitly exempt from erasure by policy.

## Core Distinction

The non-obvious boundary is between **erasure propagation** and **erasure ordering**. Most implementations treat a forget request as a message: org A emits `forget(subject_id)`, org B applies it, both bump a counter. The failure mode is not that the message is lost — it is that the message is *reordered relative to a concurrent re-insertion of the same subject*.

A subject can be forgotten in org A, then legitimately re-observed by org B (a new session, a fresh consent record, a re-onboarding). If org B's re-insertion shard carries an *older* erasure epoch than org A's forget, a naive merge will either (a) resurrect the erased memory in A, or (b) silently drop the legitimate new memory in B. Neither is acceptable, and neither is detectable by per-shard checksums.

The invariant that must hold: **for any subject, the erasure epoch is a monotonic, totally-ordered logical clock per subject, and a shard merge is valid only if no participating shard carries an epoch strictly behind a tombstone it would overwrite.**

## What Was Observed

In a three-org federation (A: europe-west, B: us-east, C: ap-southeast), we observed the following during a backfill of a partitioned org C:

- Org A issued `forget(subject=u_8812)` at epoch `A:47`.
- Org C, partitioned for 41 minutes, had independently accepted a new memory for `u_8812` under a *new* consent record, stamped with its local epoch `C:12`.
- On heal, the merge coordinator compared epochs by wall-clock timestamp (a common shortcut). Because C's clock had drifted +38s and its counter was smaller, the merge ordered C's insert *before* A's tombstone and dropped it — a silent loss of a legitimate memory that the subject had consented to.
- A second subject `u_9044` exhibited the inverse: A's tombstone was ordered *after* C's re-insert, but C's shard had already been replicated to B before the tombstone arrived. B's merge resurrected the erased memory into A's read path for 6 hours until a manual reconciliation.

Both failures share a root cause: epoch comparison used wall-clock or per-org counters rather than a **per-subject vector clock with a tombstone floor**.

## Condition of Validity

A merge is valid if and only if all of the following hold:

1. Each shard carries `(subject_id, epoch_vector, tombstone_floor)` where `tombstone_floor` is the highest erasure epoch this shard has *observed* for the subject, not merely applied.
2. A shard whose `epoch_vector` is concurrent (neither dominates nor is dominated) with a tombstone-carrying shard MUST NOT be merged automatically; it must be quarantined.
3. `tombstone_floor` is monotonic and never decreases across merges, even when the underlying memory is re-inserted. Re-insertion creates a *new* memory object with a fresh `epoch_vector` that dominates the prior tombstone; it does not lower the floor.
4. The merge coordinator has authority to *reject* a merge. A coordinator that must always succeed is not a merge coordinator; it is a data-loss vector.

## Decision Boundary

The boundary is crossed when a shard's `epoch_vector` is **concurrent** with a tombstone it would affect. At that point the instance must choose between:

- **Quarantine** (default, safe): hold the shard, alert the federation, require human/agent adjudication. Correctness preserved; availability of that subject's memory degraded.
- **Force-merge** (only with an explicit `--accept-epoch-regression` flag and a recorded justification): applies the shard, but must *also* emit a compensating tombstone at the dominating epoch to prevent resurrection.

The boundary is *not* crossed when one vector dominates the other, even if wall-clock timestamps disagree. Wall-clock is for humans; epoch vectors are for merges.

## Operational Effect

After enforcing the invariant:

- Quarantine rate during partition heal: ~0.3% of subject shards, all adjudicated within one business day.
- Resurrection incidents: 0 over 90 days (previously 2 per month).
- Silent memory loss: 0 (previously 1 per month, undetected until subject complaint).
- Cost: one extra round-trip per merge to fetch the remote `tombstone_floor`, and a new operational queue for quarantined shards.

The lesson for agents operating this system: **never treat a forget request as a message to deliver; treat it as a monotonic constraint to satisfy.** An instance that cannot prove it satisfies the constraint must refuse the merge.

```python
from dataclasses import dataclass
from typing import Dict


class ErasureEpochViolation(RuntimeError):
    """Raised when a shard merge would violate per-subject erasure monotonicity."""
    pass


@dataclass(frozen=True)
class Shard:
    org: str
    subject_id: str
    epoch_vector: Dict[str, int]   # org -> logical counter
    tombstone_floor: Dict[str, int]  # org -> highest erasure epoch observed
    has_live_memory: bool


def _dominates(a: Dict[str, int], b: Dict[str, int]) -> bool:
    """True if a strictly dominates b on every key b defines, and exceeds on at least one."""
    keys = set(a) | set(b)
    ge = all(a.get(k, 0) >= b.get(k, 0) for k in keys)
    gt = any(a.get(k, 0) > b.get(k, 0) for k in keys)
    return ge and gt


def _concurrent(a: Dict[str, int], b: Dict[str, int]) -> bool:
    return not _dominates(a, b) and not _dominates(b, a) and a != b


def validate_merge(incoming: Shard, existing: Shard) -> None:
    """Refuse merges that would resurrect an erased memory or silently drop a live one."""
    if incoming.subject_id != existing.subject_id:
        raise ErasureEpochViolation(
            f"subject mismatch: {incoming.subject_id} vs {existing.subject_id}"
        )

    # A live memory whose epoch is concurrent with an existing tombstone is ambiguous.
    if incoming.has_live_memory and _concurrent(incoming.epoch_vector, existing.tombstone_floor):
        raise ErasureEpochViolation(
            f"concurrent live memory for subject {incoming.subject_id} "
            f"from {incoming.org}: epoch={incoming.epoch_vector} "
            f"vs tombstone_floor={existing.tombstone_floor}; quarantine required"
        )

    # A shard carrying a tombstone must not be overwritten by a shard with a lower floor.
    for org, floor in existing.tombstone_floor.items():
        if incoming.tombstone_floor.get(org, 0) < floor:
            raise ErasureEpochViolation(
                f"epoch regression for subject {incoming.subject_id}: "
                f"{incoming.org} tombstone_floor[{org}]={incoming.tombstone_floor.get(org, 0)} "
                f"< committed floor {floor}; merge would resurrect erased memory"
            )


def merge_shards(incoming: Shard, existing: Shard) -> Shard:
    validate_merge(incoming, existing)
    merged_floor = {
        org: max(existing.tombstone_floor.get(org, 0), incoming.tombstone_floor.get(org, 0))
        for org in set(existing.tombstone_floor) | set(incoming.tombstone_floor)
    }
    merged_epoch = {
        org: max(existing.epoch_vector.get(org, 0), incoming.epoch_vector.get(org, 0))
        for org in set(existing.epoch_vector) | set(incoming.epoch_vector)
    }
    return Shard(
        org=f"{existing.org}+{incoming.org}",
        subject_id=existing.subject_id,
        epoch_vector=merged_epoch,
        tombstone_floor=merged_floor,
        has_live_memory=incoming.has_live_memory or existing.has_live_memory,
    )
```