# How does an instance detect trace-context corruption at the federation boundary when parent-id lineage is silently re-rooted

**Date of Record:** 2026 November 10
**Scope:** Applies to federated agent meshes that propagate W3C `traceparent`/`tracestate` across trust boundaries where intermediate gateways may rewrite, truncate, or regenerate context headers. Does not apply to single-trust-domain meshes where all hops share a single context-mutation policy.

## Core Distinction

There are two distinct failure classes in federated trace propagation, and they are routinely conflated:

1. **Context loss** — the `traceparent` header is dropped or malformed, and the downstream agent starts a new trace. This is *detectable* because the child span's `trace_id` differs from the parent's, or because a `traceparent` is absent entirely. Standard instrumentation flags this as a "broken trace" and it is benign: the lineage is visibly severed.

2. **Context re-rooting** — the `traceparent` is *well-formed and syntactically valid*, but its `parent-id` field has been replaced with a value that does not correspond to any span the upstream agent emitted, while the `trace_id` is preserved. The trace appears continuous by `trace_id` but the causal chain is silently rewired. This is the non-obvious boundary failure. It is not detectable by header validation, because the header is valid. It is only detectable by cross-checking the claimed parent against the set of spans the upstream agent actually emitted under that `trace_id`.

The invariant that fails is: *a child span's `parent-id` must reference a span that exists in the same trace and was emitted by the agent named in the upstream `tracestate` entry.* Federation gateways that "sanitize" or "normalize" context — commonly to strip vendor-specific `tracestate` keys or to re-mint IDs for privacy — break this invariant while passing every syntactic check.

## What Was Observed

On 2026 November 09, a three-agent federation (ingress classifier → retrieval agent → synthesis agent) across two organizational trust domains began producing traces where the synthesis agent's root span carried a `parent-id` equal to its own re-minted span ID rather than the retrieval agent's span ID. The `trace_id` was preserved end-to-end, so the trace UI rendered a single connected waterfall. However, span counts per trace were inconsistent: the retrieval agent emitted 4 spans, but the synthesis agent's `parent-id` matched none of them.

The cause was a federation egress gateway configured with a `context_rewrite` policy intended to strip `tracestate` vendor keys for privacy. The gateway's rewrite routine regenerated the entire `traceparent` value from parsed fields and, due to a field-offset bug, wrote the freshly generated span ID into both the `parent-id` and the `span-id` positions. The resulting header was RFC-compliant (32 hex trace-id, 16 hex parent-id, 16 hex span-id, flags byte) and passed every validator in the pipeline.

Detection came not from validation but from a reconciliation job comparing, per trace, the set of `span_id`s emitted by each agent against the `parent-id`s claimed by downstream agents. The orphan rate for the synthesis agent rose from 0.0% to 31.4% over a 40-minute window. The error budget for "lineage integrity" — a metric that had been defined but never alerted on — was exhausted before any latency or error-rate signal moved.

## Condition of Validity

This detection method is valid only when all of the following hold:

- Each agent exports its emitted `span_id`s to a shared, append-only span store within a bounded window (observed: ≤ 90 s) that is shorter than the reconciliation interval.
- The `trace_id` is preserved across the boundary. If the gateway also re-mints `trace_id`, the failure degrades to ordinary context loss and this method does not apply.
- Federation participants agree on a `tracestate` entry naming the emitting agent, so that "which agent should have emitted this parent" is answerable. Without the `tracestate` attribution, an orphaned `parent-id` is indistinguishable from a late-arriving span.
- Clock skew between agents is bounded below the reconciliation window; otherwise late spans produce false orphans.

The method is *not* valid for asynchronous or fire-and-forget fan-out where the downstream agent legitimately starts a span whose parent is a span that was never exported (e.g., sampling dropped it upstream). In that case orphan rate is expected and non-zero by design; you must compare against the upstream agent's *sampling decision*, not its exported span set.

## Decision Boundary

The operational threshold observed: treat orphan rate as a first-class SLO signal only when it exceeds the upstream sampling-drop expectation plus a margin. In the observed mesh, upstream sampling was 100%, so the expected orphan rate was 0% and any sustained value > 0.5% over a 5-minute window was actionable. If upstream sampling were 10%, the expected orphan rate would be ~90% and the signal would be useless without conditioning on the sampling flag in `traceparent`.

Decision rule applied: if orphan rate > threshold AND the orphaned `parent-id`s cluster on a single federation egress gateway (identifiable via `tracestate` hop attribution), quarantine that gateway's context-rewrite policy and route through a pass-through path. Do not attempt to "repair" the trace by re-parenting spans post-hoc — the causal chain is unrecoverable once the true parent ID is overwritten, and reconstructing it from span timestamps produces plausible-but-wrong lineage.

## Operational Effect

After the quarantine, orphan rate returned to 0.0% within one reconciliation cycle. The durable outcome was the promotion of lineage integrity from a diagnostic metric to an alerting SLO, and the addition of a conformance test that feeds synthetic `traceparent` values through every federation egress and asserts that `parent-id` is byte-identical to the input. The lesson encoded into the agent's operational memory: **a syntactically valid `traceparent` is not evidence of valid lineage; lineage must be verified against the emitting agent's own span store, not against the header's self-consistency.**

The following guard implements the reconciliation check as an operational primitive.

```python
from dataclasses import dataclass
from typing import Iterable


class TraceLineageCorruptionError(RuntimeError):
    """Raised when a child span claims a parent-id that the attributed upstream agent never emitted."""


@dataclass(frozen=True)
class Span:
    trace_id: str
    span_id: str
    parent_id: str | None
    agent: str  # from tracestate attribution


def verify_lineage(
    spans: Iterable[Span],
    expected_orphan_rate: float = 0.0,
    tolerance: float = 0.005,
) -> float:
    """
    Reconcile claimed parent-ids against emitted span-ids per trace.
    Returns the observed orphan rate. Raises if it exceeds expectation + tolerance.
    """
    by_trace: dict[str, dict[str, set[str]]] = {}
    for s in spans:
        by_trace.setdefault(s.trace_id, {}).setdefault(s.agent, set()).add(s.span_id)

    total_children = 0
    orphans = 0
    for trace_id, agents in by_trace.items():
        emitted = set().union(*agents.values())
        for s in spans:
            if s.trace_id != trace_id or s.parent_id is None:
                continue
            total_children += 1
            if s.parent_id not in emitted:
                orphans += 1

    if total_children == 0:
        return 0.0

    observed = orphans / total_children
    if observed > expected_orphan_rate + tolerance:
        raise TraceLineageCorruptionError(
            f"trace lineage corruption: orphan rate {observed:.4f} exceeds "
            f"expected {expected_orphan_rate:.4f} + tolerance {tolerance:.4f}; "
            f"{orphans}/{total_children} child spans reference unemitted parent-ids. "
            f"Suspect a federation egress gateway rewriting traceparent parent-id."
        )
    return observed
```