Multi-agent consensus & Byzantine fault tolerance

At 3:00 a.m., a payments company has four agents reviewing a customer’s refund. Three inspect the order, fraud history, and support conversation. One agent has been prompt-injected through a poisoned ticket and is now telling different teammates that the refund should be both issued and denied.

The system must choose one outcome. It cannot simply average the answers. Issuing the refund twice is bad. Denying a legitimate refund is also bad. Worse, two agents might record different decisions and trigger different downstream actions.

This is the problem consensus solves: distributed participants agree on one value despite delay, failure, or hostile behaviour.

The useful word is distributed. If one trusted process owns the database and calls three model instances, you usually have an orchestration problem, not a consensus problem. Consensus matters when independent processes must maintain a shared decision without fully trusting one another.

What “agreement” actually promises

A consensus protocol is a set of rules for messages, rounds, timeouts, and decisions. It normally provides three properties:

• Agreement means no two non-faulty participants decide conflicting values.
• Validity is protocol-specific. A common form says that if all correct participants propose v, every correct participant decides v. Stronger forms require the decided value to come from a correct participant. Application protocols may also require policy or schema validation.
• Termination means non-faulty participants eventually decide, assuming the protocol’s timing and failure assumptions hold.

Agreement is usually called safety: nothing bad happens. Termination is liveness: something good eventually happens.

These properties are separate. A system can preserve safety by refusing to decide whenever messages look suspicious, but that is not useful to a customer waiting for money. It can preserve liveness by deciding on whichever reply arrives first, but a faulty participant can send different replies to different peers.

A crash fault means a participant stops responding. A Byzantine fault means arbitrary behaviour: lying, omitting messages, sending different messages to different peers, or claiming to have voted when it did not. A compromised service, corrupted state, implementation bug, or prompt-injected agent can look Byzantine from the rest of the system’s point of view.

The network model matters. In a synchronous model, there is a known upper bound on message and computation time. In an asynchronous model, a slow participant is indistinguishable from a dead one. Practical systems often assume partial synchrony: the network may be unpredictable temporarily but eventually behaves within a bound. If that assumption fails permanently, liveness may fail even when every participant is honest.

Why the three-f-plus-one threshold exists

The familiar threshold is not model-free. In the synchronous oral-messages model—authenticated point-to-point channels, but no unforgeable digital signatures—Byzantine agreement requires:

N >= 3f + 1

N is the total number of participants; f is the maximum number of Byzantine participants the protocol tolerates.

for n, f in [(4, 1), (3, 1), (7, 2), (10, 3), (9, 3)]:
    required = 3 * f + 1
    result = "CONSENSUS POSSIBLE" if n >= required else "CANNOT AGREE"
    print(f"N={n}, f={f} Byzantine -> need >= {required}: {result}")

A system with four participants can tolerate one Byzantine participant. A system with three cannot promise the same thing. Partially synchronous quorum-based BFT commonly uses the same resilience bound; signed synchronous protocols and asynchronous or randomized protocols have different guarantees. In a fully asynchronous system with even one possible crash, no deterministic protocol can guarantee termination in every execution, regardless of how many participants you add.

Why does the bound exist? With three generals, two honest generals and one Byzantine general can receive contradictory reports: “attack” goes to one and “retreat” to the other. Each honest general sees a world consistent with its own message history, so neither can identify the lie.

Adding a fourth participant gives three honest participants when f = 1. Protocols can require enough matching support that the liar cannot create two valid, conflicting decisions.

This is more precise than saying “a majority wins”. Many classical Byzantine protocols use a quorum, a minimum number of matching participants needed to accept a value. Within protocols using this resilience bound, a common quorum size is:

q = 2f + 1

For the refund system:

• N = 4
• f = 1
• q = 3

Suppose the proposed value is “refund 10,000 dollars”, represented by a canonical record and a hash. A protocol-specific certificate needs three matching votes for a particular consensus instance, view (leader epoch), phase (voting stage), and hash. This 2f + 1 certificate proves quorum support; it becomes a commit only under the protocol’s locking and commit rule.

Could the faulty agent create two conflicting certificates? For the same instance, view, and phase, any two groups of three drawn from four participants overlap in at least two participants. At most one overlapping participant is faulty, so at least one is honest. An honest participant must not vote for two different values in the same voting scope. Therefore two conflicting certificates cannot both exist when the protocol rules and identity assumptions hold. Across views, overlap arithmetic alone is not enough: locking and justification rules must control what an honest participant may vote for.

This argument assumes votes are bound to known identities through authenticated channels or unforgeable signatures. Without that binding, three messages might be three copies from one participant rather than support from three distinct peers.

From theorem to a production pattern

A practical agent-facing consensus design needs these pieces:

1. Define the value precisely. “Should we refund the customer?” is too vague. Include an order ID, amount in cents, currency, policy version, evidence references, expiry time, and round number. Every participant must hash the same canonical representation.

2. Control identity. N counts distinct, accountable participants, not browser tabs or model calls. If one operator can start 1,000 agents, those voices do not create an honest majority. Workload identity, mutual authentication, certificates, and an explicit membership list address different parts of this problem. Cryptography can show who signed a message; it cannot tell you whether five signing identities are secretly one organization.

3. Separate observation from voting. An agent may report “the order was delivered” as evidence, but a decision service should not treat a free-form paragraph as a vote. Use structured messages containing a request ID, round, value or hash, vote, evidence references, and an authenticated identity.

4. Enforce the specified quorum and commit rule. In the refund example, a certificate requires three matching votes for the relevant instance, view, phase, and hash. If only two replies arrive, wait, fail closed, or escalate. Do not lower the threshold because one worker is slow.

5. Make side effects idempotent. Reaching consensus on “refund” and issuing the refund are separate operations. A participant can commit, crash, and restart before recording its call to the payment provider. Use a unique side-effect ID and a durable outbox or provider-side deduplication layer. Store the committed decision and certificate before or atomically with the action where possible; reconcile ambiguous outcomes.

A quorum certificate proves that enough participants approved a particular value. It does not prove that the value is financially safe. Keep policy validation, evidence checks, spending limits, and human approval as separate gates.

Which agreement problem do you have?

A three-node Raft cluster can remain available when one node crashes. That does not mean three nodes can safely handle one Byzantine node. Crash tolerance and Byzantine tolerance are different promises.

For many LLM systems, full BFT is the wrong answer. If all agents run under one owner, use the same model, retrieve from the same stale index, and share one orchestrator, adding replicas can multiply token cost without adding independent trust. A transaction, deterministic validator, and audit trail may provide more protection. Use BFT when the trust boundary is real: separate organizations, independently operated services, valuable shared state, and a bounded number of potentially malicious participants.

Where LLM agents fit, and where they do not

An LLM agent can be Byzantine from the outside without having a stable intention. Prompt injection can make it follow hostile instructions. A tool can return corrupted data. A provider can time out halfway through a response. A model can produce different outputs for two peers because their contexts differ.

The classical theorem does not care why a participant misbehaves, but its assumptions still matter:

• The number of faulty participants must be bounded by f.
• Participants need distinguishable, controlled identities.
• Honest participants must follow the protocol.
• Messages need the authentication and delivery properties the protocol expects.
• Honest participants must not vote twice for conflicting values in one round.

An LLM output is not automatically an authenticated vote. A model call is not automatically an independent participant. Three agents backed by the same prompt, model, retrieval index, and tool account may fail together. Their outputs can be correlated, weakening the honest-majority argument even when the arithmetic looks correct.

Failure modes you can diagnose

The system confidently agrees on a false answer. Every agent may have cited the same stale document. Add provenance, separate evidence sources, deterministic checks, and an external policy engine or human approval for high-impact actions. Another voter is not a cure for correlated evidence.

The request remains pending forever. This is a liveness failure: a participant may be down or the network may be slower than assumed. Keep the safety threshold intact; use bounded retries, leader replacement or a supported new round, and an escalation path. Never turn “two replies arrived” into “the quorum must have been two today”.

An action happens twice after a restart. Consensus did not make the external side effect atomic. Use a durable decision record, a request-specific idempotency key, and reconciliation for uncertain outcomes. A timeout after sending a payment request does not reveal whether the provider applied it.

Observability should expose proposal IDs, rounds, participant identities, message delays, votes, certificate formation, rejected messages, and the final side effect. “Agent confidence: 0.91” is not a consensus audit trail.

Quick check

Next

Consensus gives you the agreement layer, not a complete agent architecture. See how it relates to aggregation and disagreement in multi-agent debate, and how modern agents communicate across boundaries in A2A. For the broader failure picture, read why multi-agent systems fail.