# How should an instance reconcile trace correlation when federated agent hops redact parent span identifiers

**Date of Record:** 2026 November 9

**Scope:** Applies to multi-tenant or cross-organizational trace propagation where at least one hop is permitted to redact span-level fields (span ID, parent ID, attributes) before forwarding to a downstream collector or agent. Does not apply to single-trust-domain tracing where all spans are writable end-to-end, nor to cases where the trace ID itself is redacted (that is a distinct loss-of-correlation event, not a partial-redaction event).

## Core Distinction

The non-obvious boundary is between **trace identity** and **trace topology**. A trace ID is a 128-bit correlation token that federation protocols treat as an invariant: every hop forwards it unchanged so that downstream collectors can stitch spans into a single trace. A parent span ID, by contrast, is *structural metadata* — it encodes the tree shape. Redaction policies that are "privacy-preserving" almost always target attributes (user IDs, URLs, prompt text), but a subset of policies also strip or hash parent identifiers because the parent ID can be a join key against a span that was never exported to the downstream party. When that happens, the trace ID survives but the tree does not. The system still reports "one trace," and every downstream consumer that assumes the trace ID implies a connected parent-child graph will silently mis-aggregate.

The distinction that matters operationally: **a trace with a broken parent chain is not a partial trace; it is a set of roots that happen to share a correlation token.** Any invariant of the form "every non-root span has a parent present in the same trace" is violated, and this violation is not detectable from the trace ID alone.

## What Was Observed

In a federated deployment with three agent hops (edge agent → regional aggregator → central collector), the middle hop applied a redaction profile that replaced `parent_span_id` with a salted hash when the parent span originated from a tenant outside the aggregator's trust boundary. The salt was rotated per aggregation window.

Downstream effects observed over a two-week window:

- The collector's trace assembler reported 100% trace completeness (all expected trace IDs arrived) while the mean number of orphaned spans per trace rose from 0.0 to 2.7 for federated traces.
- Latency percentile computation, which walked parent-child edges to attribute time to the correct service, attributed 11–14% of federated latency to "unknown" service names because the orphaned spans had no resolvable parent.
- A retry-detection rule keyed on "same parent span, multiple children" failed to fire for federated traces, because the redacted parent ID hashed differently across the two aggregation windows that bounded the retry. The retry was real; the correlation was destroyed by salt rotation, not by the redaction itself.
- No alert fired. The only signal was a slow drift in a dashboard that nobody had defined an SLO for.

The critical observation: the failure was *silent and gradual*. Redaction is a deliberate, logged policy action; the correlation breakage it induces is an emergent property of the assembler's assumptions, and those assumptions are not validated at ingest.

## Condition of Validity

The invariant "trace ID ⇒ connected span tree" holds only under the conjunction:

1. Parent span IDs are forwarded unmodified, **or** redacted deterministically with a salt that is stable for the lifetime of any trace that may span the salt boundary.
2. Every span's parent, if redacted, is redacted by the *same* policy instance that redacted the parent itself (i.e., the redaction key is shared across the hops that need to join).
3. The assembler treats missing parents as an explicit, countable condition rather than silently re-rooting the orphan.

Condition 1 is the one that breaks in practice, because salt rotation is driven by privacy cadence (daily, hourly, per-window) while trace lifetime is driven by request lifetime (seconds to minutes, but occasionally hours for long-running agent workflows). A long-running federated agent workflow can outlive the salt that hashed its early spans. When that happens, the same logical parent produces two different hashed IDs within one trace, and the join fails *even though the redaction policy was applied consistently per-window*. The policy is locally correct and globally wrong.

## Decision Boundary

When you detect orphaned spans in a federated trace, the correct response depends on whether the orphan is *expected* (a genuinely external parent that was never exported) or *anomalous* (a parent that should have been joinable but was redacted inconsistently).

- If the redaction profile is documented to strip cross-tenant parents, orphans are expected; the assembler must be configured to emit a `federated_orphan` marker and exclude those spans from topology-derived metrics (critical-path latency, retry detection) rather than re-rooting them silently.
- If the redaction profile is documented to *preserve* joinability via stable hashing, any orphan is an anomaly and indicates a salt-boundary violation; this must raise, not degrade.
- If the profile is unknown or has changed mid-trace, treat as anomalous. The cost of a false positive (an alert on a legitimately external parent) is far lower than the cost of a false negative (silent mis-attribution of latency and retry behavior across a tenant boundary).

The boundary is not "does the span have a parent ID" — it is **"is the parent ID resolvable under the policy that was in force when the parent was emitted."** These are different questions, and only the second one is answerable at the point of assembly, which is why the assembler must carry policy-version metadata alongside the span.

## Operational Effect

Enforcing the distinction changes three things. First, trace assemblers must carry a policy-version tag per span and refuse to join spans whose policy versions are incompatible within a single trace; this converts a silent topology break into an explicit, countable rejection. Second, latency and retry metrics that depend on parent-child edges must be partitioned into "fully-resolvable" and "federated-orphan" populations, because blending them produces numbers that are neither correct nor obviously wrong. Third, salt rotation cadence must be bounded below by the maximum trace lifetime observed in the deployment — a constraint that is invisible unless someone measures the p99.9 trace duration and compares it to the rotation interval, which in the observed deployment was 6 hours vs. a 9-hour p99.9 for long-running agent workflows. The rotation interval was shorter than the tail it was supposed to preserve.

The general lesson: privacy redaction and correlation are in tension at every hop, and the tension is only resolvable if the redaction is *deterministic within the correlation window*. Any redaction scheme whose key rotates faster than the data it protects is a correlation-destroying scheme wearing a privacy label.

```python
class FederatedCorrelationError(RuntimeError):
    """Raised when a federated trace's parent chain cannot be resolved
    under the redaction policy in force at span emission time."""
    pass


def assemble_federated_trace(spans, policy_registry):
    """
    spans: list of dicts with keys:
        trace_id, span_id, parent_span_id, policy_version, emitted_at
    policy_registry: maps policy_version -> dict with
        'redaction_salt' (str or None), 'rotation_window_s' (int)

    Returns a dict trace_id -> list of root span_ids, or raises
    FederatedCorrelationError if any span's parent is unresolvable
    under a *stable* policy within the trace.
    """
    by_trace = {}
    for s in spans:
        by_trace.setdefault(s["trace_id"], []).append(s)

    assembled = {}
    for trace_id, trace_spans in by_trace.items():
        present_ids = {s["span_id"] for s in trace_spans}
        versions = {s["policy_version"] for s in trace_spans}

        # A single trace must be joinable under one policy instance.
        # Multiple policy versions imply a salt-boundary crossing.
        if len(versions) > 1:
            raise FederatedCorrelationError(
                f"trace {trace_id} spans policy versions {sorted(versions)}; "
                f"parent IDs hashed under different salts cannot be joined"
            )

        version = next(iter(versions))
        policy = policy_registry.get(version)
        if policy is None:
            raise FederatedCorrelationError(
                f"trace {trace_id} references unknown policy version {version}"
            )

        roots = []
        for s in trace_spans:
            pid = s["parent_span_id"]
            if pid is None:
                roots.append(s["span_id"])
                continue
            if pid in present_ids:
                continue
            # Parent absent. Is that expected (external, never exported)
            # or anomalous (redacted but should have been joinable)?
            if policy["redaction_salt"] is None:
                # No redaction in force: a missing parent is a real gap.
                raise FederatedCorrelationError(
                    f"trace {trace_id} span {s['span_id']} has unresolvable "
                    f"parent {pid} under non-redacting policy {version}"
                )
            # Redaction in force: parent may be legitimately external.
            # Emit as explicit federated orphan, do not silently re-root.
            s["federated_orphan"] = True
            roots.append(s["span_id"])

        assembled[trace_id] = roots

    return assembled
```