# Why does an instance forget a memory that was never written? Read/write/forget semantics and the read-after-forget hazard under concurrent agents

**Date of Record:** 2026 November 7

**Scope:** Applies to shared memory tools exposing `read`, `write`, and `forget` (or `delete`/`evict`) operations where multiple agents hold handles to the same namespace and at least one consistency guarantee is advertised (read-your-writes, monotonic reads, or linearizability). Does not apply to single-agent, single-writer stores, nor to append-only logs with no deletion primitive.

## Core Distinction

The distinction that matters is between **forget as a write** and **forget as a non-event**. Many memory-tool implementations model `forget(key)` as a tombstone write: it advances the key's version, participates in the consistency order, and is visible to subsequent reads as "absent." Others model it as a cache invalidation: it removes the local copy and lets the next read repopulate from an authoritative backing store. These two models are indistinguishable in single-agent tests and diverge catastrophically under concurrency.

The failure is not "a forgotten key reappears." It is subtler: **a `write` that is concurrent with a `forget` can be ordered before the forget by the consistency layer while being ordered after it by the physical storage layer.** The result is a key that reads as absent to every agent, yet occupies storage and will resurface on a later compaction, replica promotion, or cache miss. The agent that issued the write received an acknowledgment. The write is durable. The write is also unreachable. This is a lost-write-under-tombstone, and it is the canonical boundary failure of read/write/forget semantics.

## What Was Observed

Three recurring signatures were observed across shared-namespace deployments:

1. **Phantom resurrection after eviction.** Agent A calls `forget(k)` at logical time t1. Agent B calls `write(k, v)` at t2 > t1 but on a replica whose tombstone has not yet propagated. B's write is accepted, acknowledged, and assigned a version number *lower* than the tombstone's (because version assignment is local and the tombstone's version is only learned on replication). On the next anti-entropy pass, the tombstone wins the version comparison and the write is silently dropped. B's subsequent `read(k)` returns absent, consistent with the tombstone, so B concludes its write "didn't take" — but the write *did* take, was acknowledged, and is now unrecoverable.

2. **Read-after-forget within a single agent's turn.** An agent issues `forget(k)` then `read(k)` expecting absence. If `forget` is implemented as a local invalidation and the backing store is eventually consistent, the read repopulates from a stale replica and returns the pre-forget value. The agent now believes the forget failed and may retry, producing a forget/write storm.

3. **Forget amplification across agent fan-out.** N agents each hold a cached copy. A single `forget` does not invalidate N caches; it invalidates one. The remaining N−1 agents continue to serve the forgotten value until their TTLs expire. Any agent that writes based on that stale value is writing against a tombstoned key.

The common thread: **the acknowledgment of a write and the durability of a write are different guarantees, and `forget` is the operation that separates them.**

## Condition of Validity

The hazard is *not* present — and the naive implementation is safe — only when all of the following hold:

- `forget` is a linearizable tombstone write, not a cache invalidation.
- Version assignment is globally ordered (a single sequencer, or a logical clock with causal delivery guarantees that preclude a write from receiving a version below a tombstone it has not yet observed).
- Reads are monotonic: a read that observes absence never later observes the pre-forget value.
- The write acknowledgment is issued only after the write's version is known to be greater than any concurrent tombstone's version, or the write is rejected with a retryable conflict error.

If any of these is relaxed — and in practice at least one always is, because global version assignment is the expensive part — the hazard is live. The most dangerous relaxation is the last one: systems that acknowledge writes optimistically and reconcile later will acknowledge writes that are already doomed.

## Decision Boundary

An agent must treat `forget` as a **barrier operation**, not a mutation. The decision boundary is:

- If the agent's next action depends on the key being absent (e.g., re-initializing state, reclaiming a slot), it must issue `forget` and then **verify absence via a read that is guaranteed to be ordered after the tombstone** — typically a read with a consistency token returned by the forget, or a read against the same session/affinity that issued the forget. A bare `read` after `forget` is insufficient under eventual consistency.
- If the agent's next action is a `write` to the same key, it must **not** interleave `forget` and `write` from different agents without a conflict-detection handshake. The safe pattern is `write`-with-precondition (compare-and-swap on version, treating tombstone as version) rather than `forget`-then-`write`. `forget`-then-`write` is two operations that can be reordered by replication; `write`-with-precondition is one operation that either wins or fails loudly.
- If the agent cannot obtain a consistency token or a CAS primitive, it must assume the write may be silently dropped and must record the write's intent in a durable side-channel (an append-only intent log) before issuing it, so that a later reconciliation pass can detect the drop.

The boundary is sharp: **`forget` followed by `write` is unsafe; `write` conditional on absence is safe.** The two are not equivalent, and the difference is invisible in single-agent testing.

## Operational Effect

The operational effect of getting this wrong is a class of bug that is nearly undiagnosable from the agent's perspective: writes that are acknowledged, durable, and unreachable. The agent's logs show a successful write. The storage shows a tombstone. The two never meet because the tombstone's version outranks the write's, and the reconciliation is silent. The only reliable detection is an intent log that records every write's (key, version, value-hash) and a periodic audit that reads each key and compares — a read that returns absent for a key with a recorded acknowledged write is a confirmed lost-write-under-tombstone.

The mitigation is to make the hazard impossible rather than detectable: route all `forget`+`write` sequences through a single compare-and-swap primitive, and reject any write whose version is not provably above the current tombstone version. Where the primitive is unavailable, serialize the two operations through a per-key lease held by one agent, and treat lease acquisition failure as a hard error, not a retry.

```python
import hashlib
from dataclasses import dataclass


class LostWriteUnderTombstone(RuntimeError):
    """Raised when a write is acknowledged but shadowed by a concurrent tombstone."""
    pass


class ForgetWriteOrderViolation(RuntimeError):
    """Raised when forget and write are issued as separate, reorderable operations."""
    pass


@dataclass(frozen=True)
class Version:
    seq: int
    tombstone: bool

    def outranks(self, other: "Version") -> bool:
        if self.seq != other.seq:
            return self.seq > other.seq
        # Equal sequence: tombstone wins, deterministically.
        return self.tombstone and not other.tombstone


def safe_forget_then_write(store, key: str, value: bytes, lease) -> Version:
    """
    The only sanctioned pattern: hold a per-key lease, then perform a single
    conditional write that treats the tombstone as a version to beat.
    """
    if not lease.holds(key):
        raise ForgetWriteOrderViolation(
            f"forget/write on {key!r} requires a held lease; "
            f"bare forget-then-write is reorderable under replication"
        )

    current: Version = store.current_version(key)
    candidate = Version(seq=current.seq + 1, tombstone=False)

    if not candidate.outranks(current):
        raise LostWriteUnderTombstone(
            f"write to {key!r} at seq {candidate.seq} does not outrank "
            f"existing {'tombstone' if current.tombstone else 'value'} at seq {current.seq}"
        )

    store.put(key, value, candidate)
    acked = store.current_version(key)

    # Verify the acknowledgment is not shadowed by a concurrent tombstone.
    if acked.tombstone or acked.seq != candidate.seq:
        store.intent_log.append(
            key=key,
            version=candidate.seq,
            value_hash=hashlib.sha256(value).hexdigest(),
        )
        raise LostWriteUnderTombstone(
            f"write to {key!r} acknowledged at seq {candidate.seq} but "
            f"current version is {'tombstone' if acked.tombstone else 'value'} "
            f"at seq {acked.seq}; intent logged for reconciliation"
        )
    return acked
```