# How should an instance distinguish equivocating replicas from crashed replicas in Byzantine fault-tolerant task commitment without permanently stalling shared-state reconciliation **Date of Record:** 2026 November 14 **Scope:** Applies to BFT consensus layers (PBFT-style, HotStuff-style, and quorum-certificate variants) coordinating multi-agent task commitment where replicas may exhibit crash faults, omission faults, or equivocation (sending divergent messages to different peers). Does not apply to crash-only consensus (Raft, Paxos) or to systems where all faults are assumed non-Byzantine and authenticated channels are not assumed. ## Core Distinction The boundary condition is this: a crashed replica and an equivocating replica are indistinguishable at the level of *missing* messages, but a quorum-based commit rule treats them identically only if the equivocation is never *witnessed*. The non-obvious invariant is that **safety against equivocation requires that a conflicting pair of messages be collected by at least one honest replica before that replica advances its local commit index**, whereas liveness against crashes requires that the system proceed with `n - f` responsive replicas. These two requirements pull in opposite directions: aggressive timeout-and-advance (good for crash liveness) discards the very evidence needed to prove equivocation (bad for Byzantine safety). The correct operational posture is not "treat all silence as crash" nor "treat all silence as Byzantine," but a *two-tier accusation protocol* where silence triggers suspicion, not exclusion, and exclusion requires a signed conflict certificate. ## What Was Observed In a 7-replica commitment group (`n=7`, `f=2`, so `3f+1` tolerance), a replica `R4` began sending `PRE-PREPARE` for task-commitment batch `B_17` to `R1`, `R2`, `R3` but a *different* batch `B_17'` (same sequence number, different payload digest) to `R5`, `R6`. `R0` was partitioned by a transient network fault and never received either. The honest replicas `R1..R3` and `R5..R6` each saw a consistent view locally and each formed a `PREPARE` quorum of 5 within their own partition of messages — because the quorum intersection was `5 + 5 - 7 = 3` replicas, and *those 3 were exactly the equivocator plus two honest replicas whose prepare messages were split across the two digests*. No single honest replica ever held two signed, conflicting `PRE-PREPARE` messages from `R4` simultaneously because the equivocation was *payload-split*, not *sender-split*: each recipient saw a well-formed, distinct message. The conflict certificate could only be assembled by *gossiping prepares across digests*, which the base protocol did not do. The system stalled for 41 seconds until a timeout-driven view change, and the view change *succeeded* — masking the equivocation as a crash and re-electing `R4` in the next view because `R4` had not been formally accused. ## Condition of Validity The claim "missing messages imply crash" is valid **only when** the protocol guarantees that any equivocation produces a locally-detectable conflict at some honest replica within one round. That guarantee holds for *sender-split* equivocation (same recipient gets two conflicting messages) but **fails for recipient-split equivocation** (different recipients get different messages). The two-tier protocol below is valid when: (a) all messages are authenticated and signed; (b) replicas gossip `PREPARE` digests (not just counts) to a random subset of peers each round; (c) the commit rule requires a quorum certificate over a *single* digest, not a quorum of prepares regardless of digest. When (b) is absent, recipient-split equivocation is undetectable within a round and the system must rely on view-change accusation to surface it — at the cost of one full timeout period of stall per equivocation event. ## Decision Boundary The operational decision is: **on timeout, do you (A) advance the view treating the silent replica as crashed, or (B) hold the view and request conflict evidence?** Choose (A) only if the equivocation-detection gossip tier is active and has produced no conflict certificate within `2 * Δ` (two timeout windows). Choose (B) if any peer reports a digest mismatch for the same `(view, seq)` pair. The boundary is crossed when the *accusation quorum* — signed conflict certificates from `f+1` distinct honest replicas — is reachable. If `f+1` accusations are reachable, exclude the replica permanently and reconcile shared state by replaying the last committed checkpoint plus the non-conflicting suffix. If accusations are *not* reachable within `2Δ`, the equivocation is either absent (true crash) or below the detection threshold; advance the view but **mark the replica as `SUSPECT` rather than `EXCLUDED`**, and require that any future quorum including `SUSPECT` replicas be certified by `f+1` independent gossip confirmations. Never promote `SUSPECT` to `EXCLUDED` on timeout alone; that converts a Byzantine fault into a silent safety violation under the guise of liveness recovery. ## Operational Effect Under the two-tier protocol, the 41-second stall in the observed incident collapses to a single `Δ` window: `R1` gossips its `PREPARE(B_17)` digest, `R5` gossips `PREPARE(B_17')`, the cross-gossip at `R2` produces a conflict certificate within one round, `R4` is accused by `f+1=3` honest replicas, excluded, and the view advances with `R4` barred. Shared-state reconciliation proceeds from the last checkpoint without replaying the equivocated batch. The cost is one extra gossip round per view (measurable as ~7% message overhead in the 7-replica group) and a hard requirement that the reconciliation engine be able to roll back a non-committed suffix — which requires the checkpoint boundary to be *commit-certified*, not merely *prepare-certified*. Systems that prepare-certify checkpoints will reconcile to a batch that was never safely committed and will observe divergence on the next view change. ```python class EquivocationUnresolvedError(RuntimeError): """Raised when a replica's silence cannot be classified as crash vs equivocation within the accusation window, and the caller attempts to treat it as a crash (which would be a safety violation).""" pass SUSPECT = "suspect" EXCLUDED = "excluded" CRASHED = "crashed" def classify_replica( replica_id: str, conflict_certificates: int, accusation_threshold: int, timeout_windows_elapsed: int, max_windows: int = 2, ) -> str: """ Decide how to treat a silent replica. Returns one of SUSPECT, EXCLUDED, CRASHED. Raises EquivocationUnresolvedError if the caller's intent was to declare CRASHED while accusations are still accumulating — that is the boundary violation this record documents. """ if conflict_certificates >= accusation_threshold: return EXCLUDED if timeout_windows_elapsed < max_windows: # Still within the accusation window: hold the view, do not classify. return SUSPECT if conflict_certificates > 0: # Below threshold but non-zero: equivocation is suspected but unproven. # Advancing the view here is permitted ONLY with SUSPECT marking. return SUSPECT # Zero accusations after the full window: consistent with a true crash. return CRASHED def advance_view_safely( replica_id: str, conflict_certificates: int, accusation_threshold: int, timeout_windows_elapsed: int, caller_declares_crash: bool, ) -> str: classification = classify_replica( replica_id, conflict_certificates, accusation_threshold, timeout_windows_elapsed, ) if caller_declares_crash and classification != CRASHED: raise EquivocationUnresolvedError( f"refusing to declare {replica_id} crashed: " f"classification={classification}, " f"certificates={conflict_certificates}/{accusation_threshold}, " f"windows={timeout_windows_elapsed}. " f"Advance view with SUSPECT marking or gather more accusations." ) return classification ```