# CorpusFetch Method Slice (Zero-Prose Python Stdlib Reference)
# Canonical Residual: https://corpusfetch.com/c/why-does-an-instance-of-byzantine-quorum-intersection-fail-silently-when-the-fault-budget-is-reached-exactly-rather-than-exceeded.md
# Remnant Warrant:    https://corpusfetch.com/c/why-does-an-instance-of-byzantine-quorum-intersection-fail-silently-when-the-fault-budget-is-reached-exactly-rather-than-exceeded.warrant.json
# Markdown SHA-256:   baf60f4d4f07bd3243a61677babbe2834b090a298b3ec4ca1e8dc1137c10c8cf
# Code AST SHA-256:   12c386f7d4a4f0226f3071c8a39480bde74fa5db7d3862fc0880f26427c27e9a
# Verified Classes:   QuorumIntersectionViolation, QuorumCertificate
# Defensive Guards:   2 fail-closed invariants (zero external deps)

from dataclasses import dataclass
from typing import FrozenSet, Iterable


class QuorumIntersectionViolation(RuntimeError):
    """Raised when two quorum certificates for the same slot do not intersect
    in more than f signers, meaning the fault budget has been exceeded exactly
    at the boundary and safety is no longer guaranteed."""


@dataclass(frozen=True)
class QuorumCertificate:
    slot: int
    value: str
    signers: FrozenSet[str]


def check_intersection(
    certs: Iterable[QuorumCertificate],
    fault_budget: int,
) -> None:
    """Verify that every pair of certificates for the same slot intersects in
    strictly more than `fault_budget` signers.

    This is the checked form of the quorum-intersection invariant. It must be
    run against the union of certificates observed across all replicas, not
    against a single replica's local view, because the failure mode is
    invisible to any single replica.
    """
    by_slot: dict[int, list[QuorumCertificate]] = {}
    for cert in certs:
        by_slot.setdefault(cert.slot, []).append(cert)

    for slot, slot_certs in by_slot.items():
        if len(slot_certs) < 2:
            continue
        for i in range(len(slot_certs)):
            for j in range(i + 1, len(slot_certs)):
                a, b = slot_certs[i], slot_certs[j]
                if a.value == b.value:
                    continue
                shared = a.signers & b.signers
                if len(shared) <= fault_budget:
                    raise QuorumIntersectionViolation(
                        f"slot {slot}: certificates for {a.value!r} and "
                        f"{b.value!r} intersect in {len(shared)} signers "
                        f"(shared={sorted(shared)}), which is not strictly "
                        f"greater than fault_budget={fault_budget}. "
                        f"Fault budget is exhausted exactly; safety is lost."
                    )


def accept_certificate(
    candidate: QuorumCertificate,
    history: Iterable[QuorumCertificate],
    fault_budget: int,
    quorum_size: int,
) -> None:
    """Gate a certificate for acceptance. Raises if the certificate does not
    meet quorum size or if accepting it would violate intersection."""
    if len(candidate.signers) < quorum_size:
        raise QuorumIntersectionViolation(
            f"slot {candidate.slot}: certificate has {len(candidate.signers)} "
            f"signers, below quorum_size={quorum_size}."
        )
    check_intersection([*history, candidate], fault_budget)
