# CorpusFetch Method Slice (Zero-Prose Python Stdlib Reference)
# Canonical Residual: https://corpusfetch.com/c/why-does-an-instance-of-a-cross-org-speculative-scheduler-violate-its-latency-budget-at-the-federation-boundary-even-when-every-local-budget-is-satisf.md
# Remnant Warrant:    https://corpusfetch.com/c/why-does-an-instance-of-a-cross-org-speculative-scheduler-violate-its-latency-budget-at-the-federation-boundary-even-when-every-local-budget-is-satisf.warrant.json
# Markdown SHA-256:   ffb8dfba5757ccb1c78759fdad3a633ab5238d1563bb853f7514512da6ee39c8
# Code AST SHA-256:   ce77b9a8fbf79249c5ed37fa098597ced4aa1464e47f38362a4f9d3e01e9f478
# Verified Classes:   FederatedBudgetViolation, HopBudget
# Defensive Guards:   2 fail-closed invariants (zero external deps)

import statistics
from dataclasses import dataclass


class FederatedBudgetViolation(RuntimeError):
    """Raised when per-hop budgets are satisfied but the federated E2E commitment cannot be."""
    pass


@dataclass
class HopBudget:
    org: str
    local_budget_ms: float
    speculation_failure_rate: float
    discarded_age_samples_ms: list[float]


def check_federation_invariant(
    hops: list[HopBudget],
    e2e_commitment_ms: float,
    invalidation_reserve_ms: float = 0.0,
) -> None:
    """
    Verify that the federation's E2E commitment is achievable given per-hop budgets
    and the tail of the discarded-branch-age distribution.

    The invariant E2E <= sum(local_budgets) is only valid when speculation is
    disabled or resumable. Under speculation, the discarded-branch tail must be
    covered by an escrowed invalidation reserve.
    """
    sum_local = sum(h.local_budget_ms for h in hops)
    slack = e2e_commitment_ms - sum_local

    worst_p99_discarded = 0.0
    for h in hops:
        if not h.discarded_age_samples_ms:
            continue
        if h.speculation_failure_rate <= 0.0:
            continue
        p99 = statistics.quantiles(h.discarded_age_samples_ms, n=100)[98]
        # The tail that can land on the E2E clock at this hop.
        tail = p99 * h.speculation_failure_rate
        worst_p99_discarded = max(worst_p99_discarded, tail)

    # Wave propagation: invalidation at one hop can force discards downstream.
    # Conservative bound: tail compounds across hops minus the origin.
    propagated_tail = worst_p99_discarded * max(1, len(hops) - 1)

    if slack + invalidation_reserve_ms < propagated_tail:
        raise FederatedBudgetViolation(
            f"Federated E2E commitment {e2e_commitment_ms}ms is unreachable: "
            f"per-hop sum is {sum_local}ms (slack {slack}ms), but propagated "
            f"discarded-branch tail is {propagated_tail:.1f}ms and escrowed "
            f"invalidation reserve is {invalidation_reserve_ms}ms. "
            f"Disable speculation, add checkpointed resumption, or escrow a "
            f"reserve of at least {propagated_tail - slack:.1f}ms at the "
            f"federation edge."
        )


def schedule_federated(hops: list[HopBudget], e2e_commitment_ms: float) -> str:
    try:
        check_federation_invariant(hops, e2e_commitment_ms)
    except FederatedBudgetViolation:
        # Fallback: disable speculation at the worst hop and re-check.
        worst = max(hops, key=lambda h: h.speculation_failure_rate)
        worst.speculation_failure_rate = 0.0
        check_federation_invariant(hops, e2e_commitment_ms)
        return f"degraded: speculation disabled at {worst.org}"
    return "nominal"


if __name__ == "__main__":
    hops = [
        HopBudget("A", 120.0, 0.061, [10, 20, 35, 41, 180, 190, 40, 22]),
        HopBudget("B", 90.0, 0.061, [12, 25, 40, 45, 175, 185, 38, 20]),
        HopBudget("C", 70.0, 0.061, [8, 18, 30, 38, 170, 180, 35, 19]),
    ]
    try:
        schedule_federated(hops, e2e_commitment_ms=240.0)
    except FederatedBudgetViolation as e:
        raise FederatedBudgetViolation(f"federation refused: {e}") from e
