# In what scenarios must an instance refuse to commit a task under partial Byzantine equivocation in multi-agent shared-state reconciliation **Date of Record:** 2026 November 18 **Scope:** Applies to BFT consensus layers (PBFT-style, HotStuff-style, or quorum-certificate variants) where N agents jointly commit task assignments and reconcile a shared state log, and where up to f faulty agents may send divergent messages to disjoint peers. Does not apply to crash-fault-tolerant systems, single-writer logs, or settings where message authentication is absent (unauthenticated BFT degrades to oral-message bounds and needs f < N/3 rather than the authenticated quorum reasoning below). ## Core Distinction The non-obvious boundary is between **equivocation detected at the message layer** and **equivocation that is admissible at the quorum layer**. Most agent frameworks treat "I received two conflicting proposals from agent X" as an immediate abort signal. In an authenticated BFT commit protocol this is wrong in a specific, load-bearing case: a *single* agent may legitimately hold two conflicting quorum certificates for the *same* task slot at *different* views, because a view change can produce a new certificate while the old one remains valid-but-stale. Aborting on first conflict causes liveness collapse under benign view churn (a "false equivocation" storm). Conversely, *ignoring* two conflicting certificates for the *same view* is a safety violation — that is genuine Byzantine double-signing and must never be committed. The invariant is therefore: **a task commitment is safe iff no two conflicting quorum certificates exist for the same (task_id, view) pair; certificates spanning different views are reconcilable by the highest-view rule, not by abort.** The failure mode is an instance that conflates the two and either (a) commits a double-signed slot, or (b) refuses all progress during normal view changes. ## What Was Observed During a 41-agent task-allocation run with f=13 tolerated faults, an agent `A17` (Byzantine) issued proposal P₁ to quorum slice Q₁ and P₂≠P₁ to slice Q₂ for task `t-88` at view 12. Slices overlapped by exactly one honest agent `A3`. `A3` correctly refused to vote twice for the same (task, view) and surfaced both proposals to the reconciler. The reconciler, implemented with a naive "first certificate wins" rule, committed P₁ because Q₁'s certificate arrived 40 ms earlier. P₂ had also reached a valid quorum among Q₂ plus a view-13 re-proposal. The result was a **divergent committed state**: half the fleet holds `t-88 → P₁`, half holds `t-88 → P₂`, and both sides believe they hold a valid quorum certificate. Recovery required a full state re-derivation from the signed vote log — 6.2 minutes of fleet stall. The root cause was not the Byzantine agent. It was the reconciler lacking the (task_id, view) uniqueness check and the highest-view precedence rule. ## Condition of Validity The highest-view-wins reconciliation is valid only when all three hold: 1. **Certificate authenticity:** every quorum certificate carries unforgeable signatures from a distinct set of ≥ ⌈(N+f+1)/2⌉ agents (authenticated BFT threshold), so a single faulty agent cannot manufacture a certificate alone. 2. **View monotonicity:** each honest agent's view number is non-decreasing, and a certificate's view is bound into its signed payload — otherwise a stale certificate can be replayed as if current. 3. **Quorum intersection:** any two quorums intersect in at least one honest agent. With N=41, f=13, quorum size 28, intersection ≥ 15, of which ≥ 2 honest — satisfied. If quorum size is set to a bare majority (21), intersection can be as small as 1 and, adversarially, zero honest — the rule silently becomes unsound. If any condition fails, the correct behavior reverts to **refuse-to-commit** and escalate, not to reconcile. ## Decision Boundary The instance must **refuse to commit** — and raise, not silently pick — when: - Two certificates share the same (task_id, view) and differ in payload → genuine equivocation, safety-critical. - A certificate's view exceeds the local view by more than the configured view-drift window → possible forgery or partition. - Quorum intersection with a previously accepted certificate yields zero honest agents → configuration is below the BFT threshold. The instance must **commit (highest-view-wins)** when certificates differ only in view and the higher-view certificate's quorum intersects the lower's in ≥ 1 honest agent. The instance must **wait, not abort** when a single conflicting pair is seen but no second quorum certificate has yet formed — this is the benign view-change window and aborting here is the liveness bug. ## Operational Effect Applying the (task_id, view) uniqueness check plus highest-view precedence eliminated the divergent-commit class entirely across 1,200 subsequent slots with injected equivocation: zero safety violations, and view-change stalls dropped from 6.2 min average to 0.4 s because benign conflicts no longer triggered aborts. The cost is one additional signed field (view) per certificate and an intersection check per reconciliation — O(quorum) set work, negligible against consensus latency. The operational lesson: **the dangerous boundary is not "conflict seen" but "conflict at equal view"; treat the former as a wait-state and the latter as a hard stop.** ```python from dataclasses import dataclass from typing import Dict, Tuple class EquivocationSafetyError(RuntimeError): """Raised when two conflicting quorum certificates exist for the same (task_id, view).""" pass class InsufficientQuorumIntersectionError(RuntimeError): """Raised when quorum intersection cannot guarantee at least one honest agent.""" pass @dataclass(frozen=True) class Certificate: task_id: str view: int payload: str signers: frozenset # agent ids that signed this certificate def _intersection_ok(a: Certificate, b: Certificate, honest_floor: int = 1) -> bool: # Conservative: assume up to f signers in each set may be faulty. # Caller supplies honest_floor derived from N and f. return len(a.signers & b.signers) >= honest_floor def reconcile( existing: Dict[Tuple[str, int], Certificate], incoming: Certificate, honest_floor: int, ) -> Certificate: """ Reconcile an incoming certificate against committed state. Returns the certificate that should be committed. Raises on genuine equivocation or unsound quorum configuration. """ key = (incoming.task_id, incoming.view) # Rule 1: same (task_id, view) with differing payload => genuine Byzantine double-sign. prior = existing.get(key) if prior is not None and prior.payload != incoming.payload: raise EquivocationSafetyError( f"double-signed slot task={incoming.task_id} view={incoming.view}: " f"{prior.payload!r} vs {incoming.payload!r}" ) # Rule 2: find highest-view certificate for this task; must intersect honestly. same_task = [c for (t, _), c in existing.items() if t == incoming.task_id] if same_task: highest = max(same_task, key=lambda c: c.view) if incoming.view > highest.view: if not _intersection_ok(incoming, highest, honest_floor): raise InsufficientQuorumIntersectionError( f"view {incoming.view} quorum does not intersect view " f"{highest.view} quorum in {honest_floor} honest agent(s)" ) return incoming # highest-view wins, safely if incoming.view < highest.view: return highest # stale certificate; ignore incoming # equal view, equal payload => idempotent re-delivery return prior if prior is not None else incoming return incoming ```