A2A-BFT: Byzantine Fault-Tolerant Consensus for Agent-to-Agent Protocols

Agent-to-Agent (A2A) protocols let autonomous agents collaborate on complex tasks, but reliable consensus in heterogeneous agent networks remains a fundamental challenge once Byzantine failures and soft faults are admitted. We propose A2A-BFT, a Byzantine fault-tolerant consensus extension for A2A protocols: a three-phase semantic consensus protocol (Propose–Validate–Commit) with fault-adaptive decision thresholds and a reputation tracker excluded by construction from the vote-counting rule. We prove safety and liveness under n ≥ 3f + s + 1 (f Byzantine, s soft faults, s ≤ f) and evaluate entirely on real LLM inference: a 7,750-task fault sweep (n=250 per cell) with four heterogeneous open-source models, spanning mathematical reasoning, code generation, and knowledge QA. On execution-validated code tasks the protocol committed no wrong answer in any within-boundary cell (0.0 ± 0.0% under every attack; per-cell 95% Wilson upper bound 1.5%), while sub-boundary settings violate safety up to 72.4% on GSM8K and 90.0% on knowledge QA, consistent with 3f+s+1 being a tight operating condition for s ≤ f; on semantically validated tasks, wrong commits within the boundary are bounded by the validation oracle's error rate (11.6–23.2% on GSM8K, 35.6–60.8% on MMLU, with 8B judges). Under collusion, unvalidated majority-voting and debate baselines commit incorrect answers in 16.7–63.4% of tasks within the boundary. Ablations identify view change as the core liveness component—removing it collapses decisions from 74.4% to 4.5% under strategic rejection (three-seed ablation)—and fault-adaptive thresholds as the safeguard against attack-induced deadlock. A measured audit shows the released reputation tracker to be decision-neutral but mis-specified as a deterrent: in the four attacked cells, 1,186 of 1,305 aggressive penalties landed on honest validators whose vote was objectively correct.