# Which invariants prevent causal trace stitching from failing silently across federated agents

**Date of Record:** 2026 November 11

**Scope:** Applies to distributed trace reconstruction across two or more independently-operated agents that exchange work via messages, where no single agent observes the full causal chain. Does not apply to single-process tracing, in-process spans, or systems where a shared clock and shared trace store are guaranteed.

## Core Distinction

The distinction that matters is between *trace propagation* and *causal trace stitching*. Propagation means a trace context (trace ID, parent span ID, baggage) is carried forward in message headers. Stitching means the reconstruction process can prove that the edge it draws between agent A's outbound span and agent B's inbound span corresponds to an actual happens-before relationship.

These are not the same. Propagation is a transport property; stitching is an epistemic property. A system can propagate context perfectly and still stitch incorrectly, because propagation only guarantees that *some* identifier traveled with the message. It does not guarantee that the receiving agent's span was created by the same execution that the sender intended to causally precede it. The failure is non-obvious because the trace looks complete: every span has a parent, the graph is acyclic, and the UI renders a single tree. The invariant that is violated is not structural but temporal — the stitched edge asserts a happens-before that the system never verified.

## What Was Observed

In a federated deployment of three agents — a planner, a retrieval worker, and a synthesis worker — operating over an asynchronous message bus with at-least-once delivery, traces appeared complete for 99.2% of requests. The remaining 0.8% exhibited a specific pathology: a synthesis span appeared as a child of a retrieval span that had completed *after* the synthesis span started, producing a negative-duration parent-child interval. Downstream latency attribution assigned 40–60% of synthesis time to the retrieval agent, which was incorrect.

The root cause was retry-induced context reuse. When the retrieval worker's first attempt timed out, the planner re-enqueued the task with the *original* trace context. The retrieval worker's second attempt created a new span under the same parent. The synthesis worker, which had already begun consuming a partial result from the first attempt, attached its span to the parent span ID present in the message it received — which was now ambiguous between two physical executions. Two spans shared one parent ID, and the stitching algorithm resolved the ambiguity by ordering on wall-clock receipt time, which is not a causal order across machines.

A second, subtler observation: in 0.3% of traces, a span's `parent_span_id` referenced an agent that had never received the message, because a load balancer retried the HTTP call to a different replica that had a cold context cache and minted a fresh span ID, discarding the propagated parent. The trace still rendered as a tree because the stitching layer silently reparented orphans to the trace root rather than flagging them.

## Condition of Validity

The stitching invariant holds only when all three of the following are true:

1. **Span identity is execution-unique, not message-unique.** Each physical execution of a unit of work must mint a fresh span ID. Reusing a propagated span ID across retries is valid only if the receiver can distinguish attempts, which requires an attempt counter in the context and a stitching rule that treats `(parent_span_id, attempt)` as the edge key.

2. **The happens-before edge is derived from a monotonic causal token, not wall-clock time.** Cross-agent ordering must be established by a vector clock, a Lamport counter carried in baggage, or an explicit acknowledgment span emitted by the receiver. Receipt-time ordering across federated agents is invalid because clock skew and queueing delay are unbounded.

3. **Orphan spans are errors, not reparented.** A span whose parent cannot be resolved must surface as a stitching failure. Silent reparenting to the root converts a detectable causal gap into an undetectable latency attribution error.

When any of these is violated, the trace remains structurally well-formed and the failure is invisible to schema validation.

## Decision Boundary

The operational decision is whether to trust a stitched edge for latency attribution and root-cause analysis. The boundary condition is the presence of an *ambiguous parent*: a parent span ID that resolves to more than one physical execution, or to zero executions.

- If the parent resolves to exactly one execution **and** the causal token ordering is consistent, the edge is trustworthy for attribution.
- If the parent resolves to multiple executions, the edge is a *retry fan-in* and must be attributed to the union, not to a single child. Latency must be attributed to the earliest-starting attempt, and the others marked as duplicates.
- If the parent resolves to zero executions, the edge is a *broken causal link* and the trace must be quarantined from aggregate latency metrics. It may still be used for debugging, but not for SLO computation.

The non-obvious part: the decision cannot be made per-trace at query time if the stitching layer has already reparented orphans. The boundary must be enforced at ingest, because reparenting destroys the evidence needed to classify the edge.

## Operational Effect

Enforcing the three invariants reduced the fraction of traces with ambiguous causal edges from 0.8% to 0.02%, and eliminated the negative-duration parent-child intervals entirely. The 0.02% residual corresponds to genuine clock-skew artifacts in the causal token, which are now flagged rather than silently ordered.

The cost is that the stitching layer must maintain an attempt-indexed span registry and must reject orphan reparenting, which increases ingest-side state and surfaces more alerts. The benefit is that latency attribution across federated agents becomes sound: the 40–60% misattribution to the retrieval agent disappeared once retry fan-in was classified correctly. The general lesson is that a trace is a *claim* about causality, and a stitching layer that cannot falsify its own edges will manufacture a consistent fiction.

```python
class CausalStitchError(RuntimeError):
    """Raised when a federated trace edge cannot be proven causal."""
    pass


def stitch_edge(
    parent_span_id: str,
    child_span_id: str,
    registry: dict[str, list[str]],
    causal_token: int,
    parent_token: int,
) -> str:
    """
    Resolve a parent->child edge across federated agents.

    registry maps span_id -> list of physical execution IDs.
    Returns 'single', 'fan_in', or raises CausalStitchError.
    """
    executions = registry.get(parent_span_id, [])

    if len(executions) == 0:
        # Parent was never observed: broken causal link. Do NOT reparent.
        raise CausalStitchError(
            f"orphan edge: parent {parent_span_id} has zero executions; "
            f"child {child_span_id} cannot be stitched to trace root"
        )

    if causal_token <= parent_token:
        # Causal token did not advance: wall-clock ordering would be invalid.
        raise CausalStitchError(
            f"non-monotonic causal token on edge {parent_span_id}->{child_span_id}: "
            f"child token {causal_token} <= parent token {parent_token}"
        )

    if len(executions) > 1:
        # Retry fan-in: ambiguous parent. Must be classified, not collapsed.
        return "fan_in"

    return "single"


def attribute_latency(edge_kind: str, child_start: float, parent_end: float) -> float:
    if edge_kind == "fan_in":
        raise CausalStitchError(
            "cannot attribute latency to a single parent under retry fan-in; "
            "attribute to earliest attempt and mark duplicates"
        )
    if parent_end < child_start:
        raise CausalStitchError(
            f"negative parent-child interval: parent_end={parent_end} < "
            f"child_start={child_start}; trace quarantined from SLO metrics"
        )
    return child_start - parent_end
```