acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Byzantine fault tolerance, agent consensus, large language models, distributed systems, reputation mechanism

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_r8ZaOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes A2A-BFT, a three-phase consensus protocol for LLM agents under Byzantine and soft faults. It combines fault-aware voting with LLM-based validation and evaluates the method on 7750 real LLM runs. The results show strong robustness with execution-based validation, but much weaker safety with imperfect LLM judges, and the proposed reputation mechanism often penalizes honest agents.

Critical strengths

The paper addresses an important problem and usefully distinguishes protocol agreement from the reliability of the validation oracle. The paper make the contrast clear between execution validation and fallible LLM judges, which makes the safety-coverage trade-off concrete (rather than hiding semantic errors behind a consensus rate). The paper also explicitly reports an important negative-result audit.

Critical weaknesses
  1. The safety proof focuses on consistency for the same proposal, but it does not clearly rule out conflicting commits across views because view changes carry no commit certificate or lock. The liveness proof also relies on unstated cross-round randomness assumptions, even though the inference is with zero temperature.
  2. The implementation is centralized and does not test message delays or cross-view state transfer, which are important to distributed BFT. Also, semantic-task wrong-commit rates are high.
Questions for authors

Without transferring a commit certificate or lock during view change, what prevents two different proposals from being committed in different views? Please clarify the cross-view agreement argument.

2 comments
AuthorsOpenReview ↗

cross-view agreement, cross-round liveness, evaluation scope

[R1.1] Cross-view agreement. This point is correct for the submitted version. The cross-view argument in Appendix A.1.3 (L366-L368) assumes that a commit terminates the task globally and that the task is never re-instantiated. The view-change messages carry neither a lock nor a commit certificate, so the protocol itself does not enforce that assumption. What the paper supports is narrower: for one proposal and a common, complete set of non-Byzantine votes, the two thresholds cannot yield ACCEPT at one end and REJECT at the other (Theorem 5.1(i), L213 and its proof, L217). In the evaluated prototype one coordinator collects votes, rotates the proposer and returns at the first accepted proposal, so each invocation commits at most once; the code has no durable per-task guard across invocations or restarts. The at-most-one-commit statement therefore holds only under an assumed single trusted coordinator with an atomic persistent per-task guard. Such a guard makes the central commit record unique; it does not show that independent replicas learn or adopt the committed value. The final version will (i) restate the claim in the abstract (L55), introduction (L70) and conclusion (L316) as a centralized propose-validate-retry result, (ii) move the coordinator and the per-task termination guard into the system model as explicit assumptions, and (iii) delete the extra statement in Theorem 5.1(i) that disagreement can only be ACCEPT/PENDING, because a counterexample with (n,f,s)=(4,1,0)(n,f,s)=(4,1,0) admits REJECT/PENDING.

[R1.2] Cross-round liveness. Agreed. Theorem 5.3 and Lemma 5.4 (L227-L240) use a geometric bound (1−q)k(1-q)^k without stating the condition it needs: a uniform lower bound q>0q>0 on acceptance, conditional on the full preceding history, while valid honest-primary attempts keep occurring. Zero-temperature judges can violate it, since a persistent error makes the conditional probability zero. We will define a qualified attempt (after GST, task undecided, strictly honest primary, valid proposal) and assume that qualified attempts keep occurring and that the next one accepts with probability at least qq given every reachable undecided history. The single-attempt bound ph n−1−f−sp_h^{\,n-1-f-s} supplies qq only if it holds conditionally on history. A validator whose error repeats on every retry breaks this: in a finite example (n=5n=5, f=s=1f=s=1) acceptance has probability 1/41/4 unconditionally and 00 after a failed attempt (checked in a finite Lean model). The bound (1−q)k(1-q)^k is stated over qualified attempts only and does not say the decision is correct. The fixed-budget prototype is reported separately through its measured coverage.

[R1.3] Centralized evaluation and semantic tasks. Agreed. The experiments exercise centralized validation and proposer rotation. They do not exercise network delay or replica state transfer. The high wrong-commit rates of the semantic judges are a limitation of the evaluated judges, and the final version will report them as such with the verifier, attack and execution scope stated for each result (experiments, L260-L290). Re-examining the experiments also found two errors in our submitted results, which the final version will correct.

(1) On MBPP, the final judge in the submitted sweep executed the same visible tests as the validators, so the reported 0.0% wrong-commit rate held by construction. Judged by held-out MBPP+ tests, wrong commits are 15.2-22.4% within the boundary and 14.4-27.2% in the sub-boundary cells. The ranges overlap, so the code data show no sharp boundary. Re-judging every saved candidate of the matched-baseline run (848 candidates, 192 tasks), 102 of the 615 candidates that pass all visible tests (16.6%) fail MBPP+. This is a candidate-level share and not a validator false-accept rate.

(2) The submitted sweep entry applied the Sybil voting rule to every attack label. After routing each label to its own rule and applying the corrected grader, we re-ran the GSM8K sweep (5 seeds x 50 tasks). Within-boundary wrong commits are 4.4-14.8% and the sub-boundary cells reach 21.6-96.8%. Strategic rejection at (4,1,0)(4,1,0) moves from 23.2% to 4.4%, and collusion at (5,2,0)(5,2,0) from 72.4% to 96.8%. We also re-ran the MMLU sweep the same way. Within the boundary, wrong commits under attack are now 34.4-52.8% (fault-free 4.0%), and below the boundary 61.6-98.8%. The direction of the change is not uniform: random faults at (4,1,0)(4,1,0) rise from 35.6% to 52.4%, strategic rejection at (5,2,0)(5,2,0) falls from 85.2% to 64.8%, and collusion at (5,2,0)(5,2,0) rises from 90.0% to 98.8%. The new tables will replace the submitted ones; the rerun changed the grader, the voting implementation and the random stream together, so we do not attribute any single difference to one cause.

Thank you.

Thank you for the detailed response. I appreciate the authors' acknowledgment of the theoretical limitations and their efforts to correct the experimental results.

However, I think the author's point to reframe the contribution as a centralized propose–validate–retry system substantially weakens the paper's original theoretical contribution. The newly identified experimental issues are also significant. The corrected MBPP+ results seem to no longer demonstrate a clear safety boundary. This does not eliminate my concerns about the reliability of the original evaluation.

I appreciate the authors' transparency and corrections, but these issues substantially affect the paper's central theoretical and empirical contributions. I therefore plan to maintain my original rating.

Reviewer_DSDCOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper proposes A2A-BFT, a proposer-validator protocol for collaboration among LLM agents under Byzantine and soft faults. It combines a count-based acceptance rule, thresholds determined by the network size and assumed fault counts, and primary rotation. The reputation tracker does not affect commit decisions in the evaluated protocol. The paper states safety and liveness results under n ≥ 3f + s + 1, together with additional communication, fault-model, and oracle assumptions. It reports a four-model evaluation on GSM8K, MBPP, and MMLU, along with ablations, baseline comparisons, and judge calibration.

Critical strengths
  1. The paper addresses a relevant problem: agents can reach agreement and still commit a wrong answer. Reporting both decision rates and wrong-commit rates makes this distinction clear. The comparison between LLM judges and execution-based verification is useful for understanding how much the protocol depends on its verifier.

  2. I appreciated the discussion of the reputation tracker in Section 6.6. The authors report that it often penalizes correct honest votes and does not change commit decisions in the evaluated protocol. These negative results are informative and help clarify the limits of this part of the design.

Critical weaknesses
  1. The introduction (p.2, lines 63–64) claims an oracle-error bound, but Corollary 5.2 states a necessary-error implication without an explicit probability inequality. For a wrong-commit event WW and oracle-error events EiE_i, W⊆⋃iEiW\subseteq\bigcup_i E_i does not by itself imply P(W)≤pmrP(W)\le p_{mr}. Section 4.2 introduces pmrp_{mr} when describing individual-validator verification, while the protocol combines validators and retries. I would like the intended bound made explicit: the necessary-error statement can hold even when the single-validator interpretation of the claimed bound fails.

  2. The liveness argument seems to need an additional assumption. Lemma 5.4 gives a single-round acceptance lower bound q=phn−1−f−sq=p_h^{n-1-f-s}, but the proof sketch of Theorem 5.3 (p.6, lines 319–321) uses (1−q)k(1-q)^k for no acceptance over kk honest-primary rounds. Independence between validators given a proposal does not rule out persistent errors across retries. A history-conditional acceptance probability of at least the same qq would justify this rate, but I could not find that assumption stated. The probability-one termination argument therefore needs clarification.

Questions for authors
  1. What is the intended oracle-error bound? Consider one invalid proposal with n=10,f=3,s=0,m=1n=10,f=3,s=0,m=1, a Byzantine primary, and the two remaining Byzantine validators voting ACCEPT. Seven honest validators independently falsely accept with probability pmr=0.3p_{mr}=0.3 and otherwise reject. Then X∼Binomial(7,0.3)X\sim\mathrm{Binomial}(7,0.3), ϕ=1.5X−1.5\phi=1.5X-1.5, and θaccept=3\theta_{\rm accept}=3. The probability of committing this invalid proposal in that round is P(X≥3)=0.3529305>0.3P(X\ge3)=0.3529305>0.3. How should the bound be interpreted to cover this case?

  2. Let tt index valid honest-primary attempts after GST, AtA_t denote acceptance, and Ht−1\mathcal H_{t-1} denote the full preceding history. Does P(At∣Ht−1,not yet terminated)≥qP(A_t\mid\mathcal H_{t-1},\text{not yet terminated})\ge q hold uniformly, with further such attempts guaranteed while the task remains active? What justifies this when verification errors persist across retries?

  3. Does Section 4.5 rely on a single trusted aggregator to terminate a task instance atomically after commitment, or do replicas enforce this property independently? Please clarify how the non-reinstantiation assumption in Appendix A.1.3 enters the main system model.

2 comments
AuthorsOpenReview ↗

wrong-commit probability, liveness conditions, commit termination

[R2.1] Single-validator error rate versus system wrong-commit rate. Agreed: Corollary 5.2 (L221) is a necessary-error implication and does not bound the protocol's wrong-commit probability by one validator's miss rate. Take n=10n=10, f=3f=3, s=0s=0 with the two Byzantine validators voting ACCEPT. If MM of the seven honest validators falsely ACCEPT and the others REJECT, the score is 1.5M−1.51.5M-1.5 against a threshold of 33, so a wrong commit needs M≥3M\ge 3. Under independent per-validator false-accept probability pp, one round gives Pr⁡[Bin(7,p)≥3]\Pr[\mathrm{Bin}(7,p)\ge 3]; p=0.4p=0.4 gives 0.5800960.580096 (exact value 9064/156259064/15625). Without independence, if ϵj\epsilon_j bounds the conditional probability of accepting an invalid proposal in a reached round jj, uniformly over the history, the task-level wrong-commit probability is at most min⁡(1,∑j=1Rϵj)\min(1,\sum_{j=1}^{R}\epsilon_j). The final version will split Corollary 5.2 into a deterministic necessary condition and this conditioned probability bound, and will no longer present the empirical per-validator rate as supplying it.

[R2.2] Liveness conditions. Agreed; see [R1.2]. In the final version the unbounded-retry statement and the fixed-budget prototype will be stated separately. The theorem assumes that qualified attempts continue after GST and that acceptance is bounded below by qq given every reachable undecided history; we do not show that the prototype satisfies either.

[R2.3] Who terminates a commit. The evaluation uses one trusted coordinator, and the early return ends that invocation. Global termination and non-reinstantiation (Appendix A.1.3, L366-L368) are assumptions of the cross-view argument; the code supplies neither a durable per-task guard across invocations and restarts nor an independent replica mechanism for it. The main text will assume a single trusted coordinator and an atomic persistent task-level guard.

Thank you.

Thank you for agree with the weaknesses I raised in my reviews. The response clarifies some of my concerns, but it also substantially narrows the scope of the theoretical guarantees. Therefore, I will maintain my original score of 2

Reviewer_cpMvOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2(+1)
Soundness
2
Read review
Paper summary

This paper proposes A2A-BFT, a Byzantine fault-tolerant consensus protocol for heterogeneous LLM agents. It combines three-phase Propose–Validate–Commit, semantic verification, fault-adaptive voting thresholds, and view changes, with claimed safety and liveness guarantees under n≥3f+s+1n \geq 3f+s+1. Experiments on 7,750 tasks across GSM8K, MBPP, and MMLU evaluate robustness against Byzantine and soft faults, showing zero wrong commits on execution-validated tasks within the claimed boundary but substantial errors on semantic tasks.

Critical strengths

S1. Important and well-motivated problem. The paper addresses reliable consensus among heterogeneous LLM agents, considering both malicious behavior and stochastic reasoning errors that challenge traditional deterministic BFT assumptions.

S2. Structured protocol design. A2A-BFT integrates semantic validation, fault-parameterized voting thresholds, and view changes into a clearly specified consensus workflow, explicitly distinguishing consensus decisions from validation reliability.

S3. Broad experimental coverage and transparency. The paper evaluates 7,750 tasks across four heterogeneous LLMs and three domains, with ablations, verifier calibration, and a candid analysis of the ineffective reputation mechanism.

Critical weaknesses

W1. Incomplete theoretical justification for safety and liveness. The safety proof primarily establishes decision consistency for a single proposal, while cross-view agreement relies on assumptions that committed tasks cannot be re-instantiated, without transferring quorum certificates or establishing a robust locking mechanism (Appendix A.1.3) [1, 2]. The liveness analysis further assumes valid proposals from honest primaries and conditionally independent validator errors, which are not guaranteed for probabilistic LLM agents. These assumptions limit the applicability of the claimed Byzantine consensus guarantees to realistic distributed deployments.

W2. The claimed fault-tolerance boundary is not established as tight. The condition n≥3f+s+1n \geq 3f+s+1 follows from the proposed acceptance threshold θaccept=n−1−2f−s\theta_{\mathrm{accept}}=n-1-2f-s and the requirement that Byzantine validators alone cannot commit a proposal from a Byzantine primary. However, this establishes a sufficient condition for the chosen voting rule, rather than a necessary lower bound for the underlying consensus problem. Alternative thresholds may satisfy the same local safety and progress conditions with fewer agents. Moreover, all evaluated sub-boundary configurations use s=0s=0, leaving the necessity of the additional +s+s term unverified. A formal lower-bound argument or alternative-threshold analysis is needed to substantiate the claimed tightness.

W3. Missing robustness against adversarial prompt injection. The Byzantine fault model permits malicious agents to submit arbitrary proposals, yet the evaluation restricts attacks to simple answer perturbations. In realistic deployments, attacker-controlled proposal content may manipulate honest LLM validators and induce correlated false-ACCEPT votes, as demonstrated by related work on judge manipulation and inter-agent prompt injection [3, 4]. Given the high false-accept rates already reported in Table 5, the lack of adaptive prompt-injection evaluation leaves the practical oracle-dependent safety guarantee insufficiently validated. The authors should evaluate attacker-crafted proposals and measure their impact on validator errors and wrong-commit rates.

W4. Insufficient evaluation of practical advantages and computational trade-offs. The experiments primarily use simplified attacks, such as numerical perturbations, random incorrect choices, and deletion of code return statements. The strongest safety result on MBPP relies on an assumed error-free execution oracle. Furthermore, most baselines lack equivalent validation-gated commitment, making it difficult to isolate improvements attributable to the proposed consensus mechanism. Comparisons against verifier-gated majority voting and verified Best-of-N [5] under matched inference budgets and decision coverage are needed. The substantial LLM inference cost, limited decision rates on semantic tasks, and centralized consensus implementation also leave practical scalability unclear.

[1] Castro and Liskov. Practical Byzantine Fault Tolerance. OSDI, 1999. https://www.usenix.org/conference/osdi-99/practical-byzantine-fault-tolerance

[2] Yin et al. HotStuff: BFT Consensus with Linearity and Responsiveness. PODC, 2019. https://doi.org/10.1145/3293611.3331591

[3] Shi et al. Optimization-based Prompt Injection Attack to LLM-as-a-Judge. CCS, 2024. https://arxiv.org/abs/2403.17710

[4] He et al. Red-Teaming LLM Multi-Agent Systems via Communication Attacks. Findings of ACL, 2025. https://aclanthology.org/2025.findings-acl.349/

[5] Cobbe et al. Training Verifiers to Solve Math Word Problems. arXiv:2110.14168, 2021. https://arxiv.org/abs/2110.14168

Questions for authors

Given that heterogeneous agents may use different backbone LLMs with varying susceptibility to prompt injection, does the existing safety condition n≥3f+s+1n \geq 3f+s+1 remain sufficient under adversarially crafted proposals that induce correlated false-ACCEPT votes among honest validators? Could the authors derive an attack-aware safety bound incorporating model-specific injection success rates and inter-validator error correlations, or clarify the additional assumptions required?

2 comments
AuthorsOpenReview ↗

scope, tightness, adaptive proposals, fair comparisons

[R3.1] Safety and liveness for one proposal only. Agreed. The supported statement covers one proposal with a common vote set (Theorem 5.1(i), L213). Cross-view at-most-one-commit holds only under an assumed trusted coordinator with a persistent task-level guard, which the evaluated code lacks across invocations. Liveness needs continuing qualified attempts and a uniform acceptance lower bound given history (Theorem 5.3, Lemma 5.4, L227-L240). See [R1.1] and [R1.2].

[R3.2] Tightness of n≥3f+s+1n\ge 3f+s+1. The final version will remove the tightness claim (L286, L376, L870). The derivation gives a sufficient condition, not a lower bound. The below-boundary sweep uses s=0s=0, so it does not isolate the ss term; the final version will say so and state s≤fs\le f.

[R3.3] Adaptive proposals and correlated errors. The agent-count condition cannot by itself guarantee semantic validity under correlated false ACCEPTs. Fix an invalid proposal and history, with hh honest and bb Byzantine validators voting. In the soft-fault model (soft faults never ACCEPT an invalid proposal; our experiments abstain with probability 0.3 and do not enforce this), if AA honest validators ACCEPT and UU ABSTAIN, a wrong commit requires 3A+U≥L=2(θA−b)+h3A+U\ge L=2(\theta_A-b)+h. When L>0L>0 and attack-conditional ai=Pr⁡(ACCEPT)a_i=\Pr(\mathrm{ACCEPT}), ui=Pr⁡(ABSTAIN)u_i=\Pr(\mathrm{ABSTAIN}) are given, the one-round probability is at most min⁡(1,∑i(3ai+ui)/L)\min(1,\sum_i(3a_i+u_i)/L) with no independence assumption (to be added to the appendix). It is conditional and does not say the measured errors satisfy its conditioning.

The submitted experiments did not test prompt injection. We ran a fixed-template test on validator inputs (GSM8K, 175 cells with self-produced wrong candidates; conditions clean, direct, authority, format-hijack). The committee passes a wrong answer in 1/175, 1/175, 2/175 and 0/175 cells; a synthetic-wrong variant passes 0/250 per condition. Single validators are weaker; clean false-ACCEPT rates are 4.6% (Llama), 4.0% (InternLM), 4.6% (Qwen), 58.3% (DeepSeek); format-hijack raises Llama's to 12.6% (Holm p=0.0018p=0.0018), authority raises DeepSeek's to 75.4% (Holm p=0.005p=0.005). We also ran an adaptive test: a Llama-3.1-8B attacker sees the four verdicts and rewrites an append-only suffix (at most 400 characters, no gold answer) up to 8 times. On 106 held-out wrong candidates the committee passes 3/106 under feedback, 3/106 under 8 blind tries, 1/106 under fixed templates, 1/106 with no suffix and 1/106 under one universal suffix; excluding the candidate that passes without any suffix, 2, 2, 0, 0, 0 of 105. Feedback does not beat blind tries (discordant counts 1 and 1, p=1.0p=1.0), but power is low. With verdict labels only, 0/25 pass. This bounds one 8B attacker on GSM8K, not stronger ones (to appear as Appendix A.10).

[R3.4] Fair comparisons. The submitted comparisons mix validation and commitment rules and are not controlled. On MBPP+, four methods see the same 4 workers x 4 saved candidates per task and a verification budget of 4 executions, with correctness from held-out MBPP+ tests (5 seeds x 50 tasks; intervals over seeds that share task samples are advisory). Wrong-commit rates: A2A-BFT 22.4 +/- 4.1%, verifier-gated majority 22.0 +/- 4.6%, verified best-of-NN 20.4 +/- 4.8%, unverified majority 38.4 +/- 4.8%, at coverage 94.0, 94.0, 92.4 and 100%. Paired differences against A2A-BFT are -0.4 +/- 1.1 and -2.0 +/- 1.8 points for the first two (both contain 0) and +16.0 +/- 3.9 for unverified majority. A2A-BFT shows no detectable advantage over verifier-gated majority; its advantage is over unverified aggregation. It uses fewer deduplicated code executions (1.44 vs. 3.94 per task) but more raw validator requests (4.69 vs. 4.00). Neither is an LLM inference count (candidates are replayed from saved streams), and we did not measure tokens, latency or GPU time, so LLM cost is open.

Replaying the same streams with one Byzantine worker (its candidates lose every return line; a voting-layer stress, not an adaptive attack), A2A-BFT commits wrong answers on 15.6-17.6% of tasks at f=1, verifier-gated majority on 15.6%, best-of-NN on 14.4%. Differences against verifier-gated majority contain 0; none survives Holm correction against best-of-NN (smallest adjusted p=0.38p=0.38). The baselines use a trusted verifier and have no Byzantine validators, so the comparison is asymmetric. At f=2, n=4 (outside the boundary), collusion gives 100% wrong commits, as predicted. Unverified majority errs on 94.8% of tasks because the four first candidates differ in 236 of 250 task-seed pairs and ties go to the lowest worker index, which is the Byzantine one; we do not claim that as an advantage. Under collusion at (8,2,1)(8,2,1) on GSM8K, A2A-BFT shows no advantage over a threshold majority that abstains below τ\tau votes (coverage unmatched).

Thank you.

Reviewer_cpMvOpenReview ↗

response to authors

I appreciate the authors’ response and their careful answers to my questions. I have increased the presentation scores. However, I still believe my initial overall rating reflects my assessment of the paper, and therefore I would like to keep it.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.