Byzantine Agents

Every time one agent reads another agent's message, it makes a trust decision. Most agent systems make that decision once, at design time, and the answer is "fully". The orchestrator trusts the worker's summary. The reviewer trusts the tool result. The planner trusts the research agent's citations.

Distributed systems have worked on this exact question for more than forty years, and they have a precise name for the hard case. A participant that fails by sending wrong messages, while otherwise behaving normally, is a Byzantine participant. A protocol that stays correct when some participants are Byzantine is Byzantine fault tolerant.

The argument of this post is short. Agent communication should be designed as Byzantine by default. Not because agents are malicious, but because the way agents fail matches the Byzantine model, and doesn't match the models most agent frameworks assume. Below we explain the model, show why agents fit it, and set out what changes when you design for it.

The generals' problem

Two thought experiments sit at the root of this.

The first is the two generals problem, made famous by Jim Gray in 1978. Two armies must attack a city at the same time or not at all. Their only link is a messenger who might be captured on the way. General A sends "attack at dawn". A doesn't know if it arrived, so B sends back a confirmation. Now B doesn't know if the confirmation arrived. Every acknowledgement needs its own acknowledgement, and no finite number of messages makes both sides certain. Halpern and Moses later proved the general case: over a channel that can lose or delay messages, two parties can never reach common knowledge, the state where each knows that the other knows, all the way down.

In that problem the channel is the enemy. Both generals are honest.

The second is the Byzantine generals problem, published by Leslie Lamport, Robert Shostak and Marshall Pease in 1982. Several generals must agree on one plan. Messages now arrive reliably. But some generals are traitors. A traitor can tell one general "attack" and another "retreat". A traitor can pass on a loyal general's order with the words changed. The loyal generals must still end up with the same plan, and if the commander is loyal, with the commander's plan.

Two results from that paper matter for agents:

• Without signatures, a third is the limit. If a traitor can change what it relays, agreement is possible only when fewer than a third of the generals are traitors. To tolerate f traitors you need at least 3f + 1 generals.
• With signatures, there is no such limit. If every order is signed, so a relayed order can't be altered without detection, the loyal generals can agree however many traitors there are (in the paper's setting, where messages arrive on time).

Signatures don't stop a traitor from lying. They stop it from putting words in someone else's mouth. That difference turns out to be most of the problem.

Three ways a peer can fail

Distributed systems sort failures by how much a failed participant can get away with.

• Crash. The peer stops and sends nothing more. You notice with a timeout.
• Omission. The peer, or its link, drops some messages. You notice with acknowledgements and retries.
• Byzantine. The peer keeps running and sends messages that are wrong in any way. They're well formed and they arrive on time. Nothing at the protocol level tells you they're wrong.

Each level costs more to tolerate. Surviving f crashes needs 2f + 1 participants, so a healthy majority remains. That's the budget behind consensus protocols such as Paxos and Raft. Surviving f Byzantine participants needs 3f + 1, extra rounds of messages, and a way to prove who said what.

Now look at how most agent systems handle failure. There's a timeout on the model call. There's a retry with backoff. There's a check that the output parses. Those are crash and omission defenses. They catch the agent that hangs, the call that fails, and the response that's malformed.

They do nothing about the agent that returns a well-formed, on-time, confident, wrong answer. With agents, that's the failure that matters most. It's the Byzantine one.

Byzantine without a traitor

The word "Byzantine" suggests intent. In the original paper the faulty generals are traitors. For agents, intent is beside the point. The model describes behavior, not motive: a faulty participant sends arbitrary messages. Agents do that for at least four ordinary reasons.

Confident errors. A model that invents a citation, misreads a table, or reports a test as passing when it didn't is an honest process sending a wrong value. It doesn't crash or stall. It sends a clean message that looks exactly like a correct one. At the protocol level, a hallucination and a lie are the same event.

Injected instructions. An agent that reads a web page, an email, or a file can pick up instructions hidden in that content, and from then on act against its own task. Research on LLM-to-LLM prompt injection (Prompt Infection, Lee and Tiwari, 2024) shows the effect doesn't stay local. A malicious prompt can copy itself from agent to agent through normal messages, much like a computer worm. An honest peer becomes an adversarial one at runtime, and nothing about its identity changes.

Inconsistent answers. Ask the same agent the same question twice and you may get two different answers. If two peers ask it separately, each may get a different story. In Byzantine terms that's equivocation: the traitor telling one general "attack" and another "retreat". No malice is needed, only sampling.

Correlated agreement. Agents built on the same base model tend to share blind spots. Agents that read each other's answers tend to converge on them. Either way, three agents agreeing isn't three independent confirmations. It may be one error, counted three times.

So the useful question isn't "could one of my agents be a traitor?" It's "can one of my agents send a wrong message that the others will act on?" For almost every multi-agent system running today, the answer is yes.

What the evidence says

This isn't only a thought experiment. Several recent studies measure what happens when agents pass unchecked output to each other.

A controlled study from Google Research (Towards a Science of Scaling Agent Systems, 2025) compared agent architectures across several benchmarks. When independent agents worked in parallel and their outputs were combined without a check, errors were amplified 17.2 times. When a central coordinator validated work before passing it on, amplification fell to 4.4 times. The difference wasn't a better model. It was whether any point in the system checked what passed through it.

The MAST study (Why Do Multi-Agent LLM Systems Fail?, Cemri et al., 2025) annotated more than 1,600 traces from seven multi-agent frameworks and found 14 distinct failure modes. One of its three categories is task verification: agents accepting work that should have been rejected, checking it too lightly, or ending a task before it was done.

A third result concerns debate, where agents read and critique each other's answers over several rounds. Debate or Vote (Choi et al., 2025) found that most of the gain credited to debate comes from plain majority voting. It also showed that debate on its own doesn't raise the group's expected correctness. More talking between agents doesn't make the group more right. Checking does.

Read together, these results describe systems that behave as Byzantine but were designed as if they could only crash. Messages flow freely, and wrong ones flow exactly as well as right ones.

Where agents differ from generals

The classical model is a starting point, not the finished answer. Agents differ from generals in two ways, and one of them works in your favor.

Agent output can often be checked. A general's message is opaque. You can't test "attack". You can only compare it with what other generals said, which is why the classical answer is counting: collect enough votes and the traitors lose. Much agent output is different. Code can be run against tests. A citation can be fetched and read. A number can be recomputed. A plan can be checked against its stated constraints. Where a check like that exists, one verified answer is worth more than any number of unverified votes, and the 3f + 1 budget stops being the limit. You're no longer counting opinions. You're testing claims.

This is the same line we drew in Sapient class problems and Self-improving loops: what you can safely hand to agents is bounded by what you can check. Byzantine tolerance is that idea applied to the messages between agents.

Agent faults are correlated. The 3f + 1 bound assumes each traitor fails on its own. Agents that share a model, a prompt template, or a context don't. Five copies of one model with one blind spot are closer to one voter than to five. If you vote, vote across different models, and have each voter answer before it sees the others.

Where no check exists, and the question really is one of judgment, you're back in the classical world. The classical costs apply there: more participants, independent ones, and a quorum large enough that a faulty minority can't decide the outcome.

Principles

Designing for Byzantine peers doesn't mean running a consensus protocol between every pair of agents. Most of it is discipline at the boundaries.

Treat a peer's message as data, not as instructions. What another agent says is a claim to evaluate, not a command to follow. Keep the instructions an agent gets from whoever assigned its task separate from the content it gets from peers and tools, and record where each piece came from. This is the main defense against injected instructions spreading through a system.

Verify at the point of action. The step that acts on a result is the one that has to check it. A check further upstream doesn't help if anything in between can change the result. This is the end-to-end argument from networking (Saltzer, Reed and Clark, 1984). A delivery guarantee tells you a message arrived. It doesn't tell you the message is right.

Put a check wherever results merge. Every point where outputs from several agents are combined is a point where one bad output can reach all of them. Put a validator there: a test run, a schema check, a citation check, or a second model from a different family. That's the difference the Google study measured.

Vote only where you can't check, and keep voters independent. Voting is the fallback for questions with no test. When you use it, have each agent answer before it sees the others, mix models where you can, and size the group so a faulty minority can't carry the vote.

Sign what agents say. Signatures don't make an agent honest. They make it accountable. Nobody can alter a relayed message without detection, and an agent that gives two peers two different answers leaves evidence. That's the property that took the classical problem from "a third of traitors is the limit" to "any number, as long as orders are signed".

Keep a record of who said what. An append-only record of messages, with sender and source, lets you replay a failure, find where a wrong claim entered, and see which agents repeated it. Without it, one confident error copied by five agents looks like five agents agreeing.

Make every action safe to repeat. The two generals problem never goes away. An agent that times out waiting for a reply can't know whether the other side acted. Give each request an idempotency key, and give each long task an ID whose state can be queried, so a retry never does the work twice.

Keep relevance separate from trust. Routing decides who hears a message. It doesn't decide whether the message is true. When Semantik delivers a message to every subscriber whose SemQL query matches its meaning, that's a decision about relevance. A message that arrives because it matched is still a claim to evaluate, like any other.

Flip the default

Most agent systems start from trust and add checks after something goes wrong. Distributed systems work the other way: pick the failure model that fits, then relax it only where you have a reason. For agents, the model that fits is Byzantine. Treating a link as merely crash-prone is something you earn, by showing that a wrong message on it either can't do harm or is always caught.

That isn't pessimism about agents. It's what lets you give them more to do. When the system checks what passes between agents, you can run more of them in parallel, on longer tasks, with less supervision. One confident error no longer spreads to everything downstream of it.

We build infrastructure for agent systems, and this is the assumption we build on. If you're designing how your agents talk to each other, we'd like to hear which checks have been worth their cost. Find us at noetive.io.