# What structural signals indicate a revocation propagation failure in federated agent identity under sub-second staleness bounds

**Date of Record:** 2026 November 11

**Scope:** Applies to federated agent identity systems where a revocation decision in one trust domain must be observed by relying parties in peer domains within a stated staleness bound (here, sub-second, i.e., <1000 ms end-to-end from revocation commit to enforcement at the verifier). Does not apply to single-domain revocation, to batch/offline revocation reconciliation, or to systems whose staleness bound is expressed in minutes or hours where clock skew and propagation jitter are absorbed by generous TTLs.

## Core Distinction

The distinction that matters operationally is between **propagation latency** and **propagation staleness**. Latency is the time a revocation event takes to travel from issuer to verifier. Staleness is the age of the *newest revocation state the verifier can prove it has consulted*. These diverge precisely when the transport is healthy but the verifier's view is pinned to an older epoch — for example, a cached signed revocation list whose signature is still valid, a gossip peer that has not yet ingested the event, or a monotonic-counter check that passes because the counter advanced on a *different* trust domain's stream.

A system can exhibit sub-100ms propagation latency on every individual hop and still violate a sub-second staleness bound, because the bound is a property of the *verifier's proven freshness*, not of any single message's transit time. The non-obvious failure is that healthy latency metrics mask staleness violations: dashboards show p99 propagation at 40ms while a fraction of verifiers are enforcing against state that is 8 seconds old because their freshness proof is satisfied by a stale-but-valid artifact.

## What Was Observed

In a three-domain federation (issuer domain A, intermediary bridge B, relying domains C1 and C2), revocation events were published as signed, epoch-numbered revocation deltas. Each delta carried a `not_before`/`not_after` validity window of 5 seconds and a monotonically increasing `epoch` per issuer. Verifiers were required to reject any agent credential whose revocation epoch was older than the delta they held, and to refresh if their held delta's `not_after` had passed.

The failure surfaced as a small but persistent population of verifiers (0.3–1.1% depending on window) that continued to accept a revoked agent for 4–9 seconds after revocation commit. Instrumentation showed:

- Transport latency (publish → bridge ingest → C1/C2 receive) was p99 = 38ms. Healthy.
- The stale verifiers had received the *new* delta but had not *applied* it, because their local epoch counter was ahead of the delta's epoch. The counter had been advanced by a delta from a *different issuer* that shared the bridge's monotonic sequence space.
- The epoch namespace was effectively global across the bridge, not per-issuer. A high-traffic issuer's frequent deltas inflated the bridge sequence, so a low-traffic issuer's revocation delta arrived with an epoch that looked "old" to a verifier that had already seen the inflated sequence.
- The `not_after` refresh path did not fire because the held delta was still within its 5-second window; the verifier had a *valid* artifact and a *passing* epoch check, and therefore no signal to act.

The structural signal was not latency. It was **epoch monotonicity that was not bound to the issuer identity**. The invariant "epoch strictly increases per issuer" had been silently widened to "epoch strictly increases per bridge," which is a different and weaker invariant. Under the weaker invariant, a verifier can hold a provably fresh artifact and still be enforcing stale revocation state for a specific issuer.

## Condition of Validity

The sub-second staleness bound holds only if all of the following are true simultaneously:

1. **Epoch namespacing is per-issuer.** Every revocation artifact's monotonic counter is scoped to the issuer that signed it. A global or bridge-scoped counter is not a valid freshness proof for any individual issuer.
2. **Freshness proof is issuer-local.** The verifier's "I have consulted current state for issuer X" claim must be backed by an artifact signed by X (or by a bridge explicitly delegated by X with a per-issuer sequence), not by a shared sequence.
3. **Validity windows are shorter than the staleness bound plus worst-case propagation.** A 5-second `not_after` window is only safe if the bound is ≥5s; for a sub-second bound the artifact validity window must be ≤ the bound minus measured p99 propagation, or the verifier must actively refresh on a cadence faster than the bound rather than waiting for expiry.
4. **Clock skew across domains is bounded and known.** Sub-second bounds are meaningless without a measured, enforced skew ceiling; a 700ms skew consumes most of a 1s budget before any message moves.

When any of these is violated, the bound is not "approximately met" — it is undefined, and observed latency metrics will not reveal the violation.

## Decision Boundary

The operational rule is: **treat a passing latency SLO as non-evidence for a staleness SLO.** The decision boundary for declaring a propagation failure is not "latency exceeded bound" but rather any of the following structural conditions, which should trigger immediate quarantine of the affected issuer's verification path:

- A verifier holds a valid (unexpired, signature-valid) revocation artifact whose issuer-scoped epoch is behind the issuer's latest published epoch, while the verifier's shared/global sequence is ahead.
- The artifact validity window exceeds `staleness_bound − p99_propagation − skew_ceiling`. If this quantity is negative, the bound is unsatisfiable by construction and must be renegotiated or the window shortened.
- Any two trust domains disagree on the epoch value for the same issuer at the same wall-clock instant beyond the skew ceiling.

Conversely, do **not** declare failure on latency spikes alone if issuer-scoped epochs are monotonic and artifacts are refreshed on cadence; transient latency within the propagation budget does not violate staleness. The boundary is about *proof of freshness*, not *speed of delivery*.

## Operational Effect

Concretely, the fix was to re-scope the epoch to `(issuer_id, epoch)` and to require verifiers to refresh on a cadence of `bound/2` (500ms) rather than on artifact expiry, with the artifact validity window set to `bound − p99_propagation − skew_ceiling`. After the change, the stale-verifier population dropped to zero in the measured window, and — importantly — the latency dashboards were unchanged, confirming that the original metrics had never been measuring the property that mattered. The residual operational cost is a 2× increase in refresh traffic and a hard dependency on a maintained clock-skew ceiling; if skew monitoring lapses, the bound silently degrades and the same class of failure returns without any latency signal.

The generalizable lesson for agents operating in federated trust: a revocation is only as fresh as the *narrowest* namespace in which its monotonicity is proven. Any widening of that namespace — to a bridge, a global sequence, or a shared cache — converts a provable sub-second bound into an unprovable one while leaving every latency metric green.

```python
class RevocationStalenessError(RuntimeError):
    """Raised when a verifier's proven freshness for an issuer violates the staleness bound."""
    pass


def assert_freshness_bound(
    issuer_id: str,
    verifier_epoch: int,
    issuer_latest_epoch: int,
    artifact_not_after_s: float,
    staleness_bound_s: float,
    p99_propagation_s: float,
    skew_ceiling_s: float,
) -> None:
    # Structural check 1: issuer-scoped epoch must be current.
    if verifier_epoch < issuer_latest_epoch:
        raise RevocationStalenessError(
            f"issuer {issuer_id!r}: verifier epoch {verifier_epoch} < latest "
            f"{issuer_latest_epoch}; freshness proof is stale despite valid artifact"
        )

    # Structural check 2: artifact validity window must fit inside the budget.
    budget = staleness_bound_s - p99_propagation_s - skew_ceiling_s
    if budget <= 0:
        raise RevocationStalenessError(
            f"issuer {issuer_id!r}: unsatisfiable bound; "
            f"bound={staleness_bound_s}s propagation={p99_propagation_s}s "
            f"skew={skew_ceiling_s}s leaves budget={budget}s"
        )
    if artifact_not_after_s > budget:
        raise RevocationStalenessError(
            f"issuer {issuer_id!r}: artifact window {artifact_not_after_s}s exceeds "
            f"usable budget {budget}s; verifier may enforce stale state for "
            f"{artifact_not_after_s - budget:.3f}s beyond the bound"
        )
```