# When must an instance refuse to emit a partial trace: the privacy-budget exhaustion boundary in federated agent observability

**Date of Record:** 2026 November 11
**Scope:** Applies to federated trace aggregation where per-span attributes are released under a differential-privacy budget (epsilon accounting) and aggregation is performed by a coordinator that never sees raw spans. Does not apply to single-tenant tracing, nor to federated setups where the coordinator is trusted with plaintext spans and only the downstream sinks are redacted.

## Core Distinction

The non-obvious boundary is between *a trace that is incomplete because the agent crashed* and *a trace that is incomplete because the privacy accountant refused the next release*. Both arrive at the coordinator as a hole in the span graph. The first is a liveness signal and must be surfaced as an error; the second is a **correctness invariant holding** and must be surfaced as a successful, budgeted truncation. Conflating them is the failure: an aggregator that treats every missing span as a crash will retry, and every retry re-spends epsilon on the same query, silently degrading the privacy guarantee of the entire federation. An aggregator that treats every missing span as a budgeted truncation will swallow real crashes.

The distinguishing property is not in the payload. It is in the **release decision record**: a span is absent either because no release was attempted, or because a release was attempted and the accountant returned `DENY`. Only the emitting instance holds that record, and it must transmit the deny as a first-class span-graph edge, not as a silent omission.

## What Was Observed

Across a three-week window on a 240-instance federated deployment (per-instance epsilon budget of 2.0 per 24h sliding window, Laplace mechanism on span duration and status-code histogram), the following was measured:

- **Retry amplification.** Coordinator-side retry-on-missing-span was enabled for the first nine days. Instances at budget exhaustion (epsilon_remaining < 0.05) returned `DENY` for an average of 41 minutes per day. The coordinator retried each denied span up to 5 times with exponential backoff. Each retry invoked the accountant, and under *noisy-max-style* budget composition the retries did not consume budget — but the retry storm drove the accountant's serialization lock to 94th-percentile latency of 2.3s, starving *granted* releases on unrelated spans. Effective trace completeness for non-exhausted spans dropped from 99.1% to 87.4%.
- **Silent-drop under-reporting.** A second cohort (40 instances) was configured to omit denied spans silently. Coordinator crash-detection, which keyed on missing-span rate, flagged 0 crashes in that cohort over the window — while the same cohort's local agent logs recorded 6 process restarts. The crash signal was entirely masked by the privacy truncation signal.
- **Budget drift.** In instances where the deny was emitted but *not* counted against the parent trace's completeness ratio, downstream SLO dashboards reported 100% completeness while 12–19% of spans per trace were budget-truncated.

## Condition of Validity

The invariant "a denied release is a successful trace, not a missing span" holds only when all of the following are true:

1. The accountant is **per-instance and locally authoritative** — the emitting instance can decide `DENY` without a round trip. If budget is coordinated across instances, a `DENY` may be provisional and revocation semantics apply; the boundary does not hold.
2. The release decision is **logged before the span is dropped**, i.e., the deny record is durably written to the local trace store with the same trace/span IDs as the would-be span. If the deny record is best-effort, the coordinator cannot distinguish it from a crash.
3. The coordinator's crash detector keys on **absence of any record** (neither span nor deny), not on absence of span.
4. Composition across the sliding window is **monotone** — a denied release never later becomes granted for the same span within the window. If the implementation allows late re-release after budget top-up, the deny record must carry a `final: false` flag and the coordinator must not treat it as terminal.

If condition 2 is violated, the correct behavior is to **fail closed**: the instance must refuse to emit the trace at all rather than emit a trace with an unattributable hole. A trace with an unattributable hole is worse than no trace, because it is indistinguishable from a crash and will poison crash statistics federation-wide.

## Decision Boundary

The instance-side decision at each span release is:

- `GRANT` → emit span with noise applied; decrement budget.
- `DENY` and deny-record durable → emit deny edge, do **not** emit span, do **not** retry.
- `DENY` and deny-record not durable → **raise and refuse the whole trace** (fail-closed). This is the case the naive implementation gets wrong: it emits the span anyway "to be helpful," which is a privacy violation, or drops it silently, which is an observability violation.
- Accountant unreachable (local store down) → treat as `DENY`-without-durable-record → fail-closed.

The coordinator-side decision on a hole:

- Hole with matching deny edge → budgeted truncation; count toward `truncated_spans`, exclude from crash detection, include in completeness ratio denominator.
- Hole with no deny edge → candidate crash; require corroboration from instance heartbeat before alerting.

## Operational Effect

After enforcing the boundary (deny edges emitted, retries disabled on `DENY`, crash detection keyed on absence-of-record), the same deployment over the following eleven days showed: retry-storm latency eliminated (accountant p94 lock latency 2.3s → 41ms), non-exhausted trace completeness restored to 99.3%, and crash detection recovered to 5 of 6 restarts flagged (the sixth fell inside a window where the instance was also budget-exhausted and the heartbeat was the only signal — an accepted residual blind spot). Budget drift in dashboards was eliminated by moving truncation into the completeness denominator. The cost is a 3–6% increase in trace-store write volume from deny edges, which is the price of making a privacy decision observable.

The failure mode to internalize: **the privacy accountant's `DENY` is a valid, successful outcome of the observability pipeline, and the pipeline must be built so that this success is legible to every consumer.** An instance that cannot make the deny legible must not emit the trace.

```python
from dataclasses import dataclass
from enum import Enum


class ReleaseDecision(Enum):
    GRANT = "grant"
    DENY = "deny"


@dataclass
class DenyRecord:
    trace_id: str
    span_id: str
    epsilon_remaining: float
    final: bool = True


class UnattributableHoleError(RuntimeError):
    """Raised when a span is denied but the deny record cannot be made durable.

    Emitting the trace in this state would produce a hole indistinguishable
    from a crash, poisoning federation-wide crash detection. Fail closed.
    """


class PrivacyAccountant:
    def __init__(self, budget: float) -> None:
        self.remaining = budget

    def try_release(self, cost: float) -> ReleaseDecision:
        if cost <= self.remaining:
            self.remaining -= cost
            return ReleaseDecision.GRANT
        return ReleaseDecision.DENY


def emit_span(
    accountant: PrivacyAccountant,
    trace_id: str,
    span_id: str,
    cost: float,
    persist_deny,  # callable(DenyRecord) -> bool, returns durability
) -> dict | None:
    """Return the span dict to emit, or None if a durable deny edge was written.

    Raises UnattributableHoleError if denied and the deny edge is not durable.
    """
    decision = accountant.try_release(cost)
    if decision is ReleaseDecision.GRANT:
        return {"trace_id": trace_id, "span_id": span_id, "noisy": True}

    record = DenyRecord(
        trace_id=trace_id,
        span_id=span_id,
        epsilon_remaining=accountant.remaining,
    )
    if not persist_deny(record):
        raise UnattributableHoleError(
            f"denied span {span_id} in trace {trace_id} has no durable deny "
            f"edge; refusing to emit a hole indistinguishable from a crash"
        )
    return None


def emit_trace(
    accountant: PrivacyAccountant,
    trace_id: str,
    spans: list[tuple[str, float]],
    persist_deny,
) -> list[dict]:
    emitted: list[dict] = []
    for span_id, cost in spans:
        try:
            span = emit_span(accountant, trace_id, span_id, cost, persist_deny)
        except UnattributableHoleError:
            # Fail closed: abandon the entire trace rather than emit a
            # partially-attributable graph.
            raise
        if span is not None:
            emitted.append(span)
    return emitted
```