09 Distributed Consensus & Task Allocation · #42 of 46

When Robots Lie

Reaching agreement when some of the voters are adversaries

Every consensus algorithm you've met so far quietly assumed everyone tells the truth. Cut that assumption, and a single robot whispering nonsense can poison the agreement of a thousand honest ones.

The fix isn't to detect the liar. It's to build a vote that doesn't care whether one exists.

A failed robot is easy. It goes dark, stops broadcasting, and the rest of the swarm routes around the silence. The dangerous failure is the one that keeps talking: the sensor that's drifted, the unit that's been spoofed, the node that has, for whatever reason, decided to broadcast a number that is confidently, fluently wrong. In the literature these are called Byzantine failures, and they are the reason robust consensus is its own field.

The liar at the table

Picture a handful of robots trying to agree on a single number: the temperature of a room, the bearing to a target, the price of a trade. The protocol is simple: tell your neighbors your value, listen to theirs, combine. Now drop one liar into the group who, instead of its true reading, broadcasts whatever it likes.

How you combine the numbers is suddenly the whole ballgame.

Mean consensus. Average everything you hear. Elegant, and catastrophically fragile: the mean weights every value equally, so one robot shouting 1,000,000 drags the entire group's agreement off a cliff. One bad actor poisons everyone.
Median consensus. Take the middle value instead. A liar can sit at the far end of the sorted list screaming its lungs out and the middle doesn't budge. As long as fewer than half the voices are lying, the honest majority still pins the median to the truth.
Trimmed mean. Throw away the most extreme readings on each end, then average what's left. It's the negotiated peace between the median's bluntness and the mean's precision.

Picture it running

This track has live canvases elsewhere; here, run the simulation in your head and watch the failure modes appear.

One liar joins. A single malicious robot replaces its honest measurement with a wild outlier and starts broadcasting.
Mean-based consensus breaks. Because the average counts every value, that one extreme reading pulls the group's converged answer steadily away from the truth. The swarm agrees, on the wrong thing.
Median-based consensus survives. The outlier sorts to the edge and stays there, powerless. The honest cluster owns the middle, so the swarm converges where it should.
Now turn up the dial. Add liars one at a time. There's a threshold: as the malicious fraction climbs toward half the neighborhood, even the median starts to slide. A median rule comfortably tolerating, say, 30% bad actors is exactly the safety margin these robust rules exist to buy you.

The lesson lands in one sentence: robust aggregation functions ignore outliers, and that's the entire trick.

Where the limit comes from

The median's "fewer than half" tolerance is a heuristic. The hard theoretical floor is stricter and worth knowing.

In theory. Byzantine consensus (the kind with provable guarantees against actively adversarial nodes) requires more than two-thirds of the agents to be honest. With $n$ agents and $f$ liars, you need $n > 3f$ . That isn't an engineering limitation you can out-clever; it's a fundamental limit of the problem.
In practice. Real swarms don't usually pay for full Byzantine agreement. They reach for the cheap robust statistics first (median, trimmed mean) and escalate to cryptographic signatures only when they need to prove a message came from who it claims, not merely outvote it.

It started with a fault-tolerant flight computer

The whole problem came out of a 1970s project to build an aircraft computer that would not lie when its parts broke. NASA funded it; the lab was at SRI International; the system was called SIFT, for Software Implemented Fault Tolerance. Robert Shostak hit the question first, in 1978, and called it the interactive consistency problem: how many computers do you need so that a clique of faulty ones cannot fool the working ones into disagreeing? He proved you need at least $3f+1$ and built a protocol that handled one liar. Marshall Pease then showed $3f+1$ is both necessary and sufficient for any number of liars. Shostak, Pease, and Lamport won the 2005 Dijkstra Prize for the work. The catchy general-and-traitor story came later, bolted onto a result that was already done.

The three combine rules, written out

Mean consensus, the standard, fragile update. Each agent $i$ averages over its neighborhood $N_i$ :

$x_i \leftarrow \frac{1}{|N_i|} \sum_{j \in N_i} x_j$

A single malicious $x_j$ pushed to infinity sends $x_i$ to infinity with it. Breakdown point: zero.

Median consensus: replace the sum with the order statistic:

$x_i \leftarrow \operatorname{median}(\{x_j : j \in N_i\})$

Tolerates corruption of up to half the values in $N_i$ before the result can be moved.

Trimmed mean: drop the $f$ highest and $f$ lowest readings, then average the survivors:

$x_i \leftarrow \frac{1}{|N_i| - 2f} \sum_{j \in \operatorname{trimmed}(N_i)} x_j$

where $f$ is the number of outliers trimmed from each tail. Choosing $f$ trades robustness (larger $f$ tolerates more liars) against resolution (larger $f$ discards more honest data).

Why three agents and one liar is already hopeless

The $n > 3f$ bound feels arbitrary until you try to beat the smallest broken case: one commander and two lieutenants, with exactly one traitor among the three. Watch it fail.

Say the commander is the traitor. He tells lieutenant B "attack" and lieutenant C "retreat." Honest B and C compare notes, each forwarding what they heard. Now B holds two conflicting orders, "attack" (from the commander) and "retreat" (relayed from C), and has no way to tell whether the commander lied or whether C is the traitor inventing a relay. C is stuck in the mirror image. Neither can act on the truth, because from the inside the two stories are identical.

Bump it to four agents with one traitor, and the honest three can outvote the lie. That gap, three fails, four works, is the $n > 3f$ line in miniature. Lamport, Shostak, and Pease proved the small case is the whole case: if you cannot solve one-commander-two-lieutenants, you cannot solve any group where liars reach a third.

Robust consensus in Rust

fn robust_consensus_step(agents: &mut [Agent], neighbors: &[Vec<usize>],
                        method: RobustMethod) {
    for i in 0..agents.len() {
        if agents[i].malicious { continue; } // honest agents only update honestly

        let values: Vec<f32> = neighbors[i].iter()
            .map(|&j| agents[j].value)
            .collect();

        agents[i].value = match method {
            RobustMethod::Mean => values.iter().sum::<f32>() / values.len() as f32,
            RobustMethod::Median => median(&values),
            RobustMethod::TrimmedMean(f) => trimmed_mean(&values, f),
        };
    }
}

A prompt to hand an LLM if you want to push past robust statistics into provable agreement:

"Implement Byzantine agreement algorithm:
- Requires >2/3 honest robots
- Uses voting and majority rule
- Test with varying malicious fractions
- Compare to median consensus"

Key takeaways

Byzantine failure is the robot that keeps talking and lies, far more dangerous than the one that simply crashes.
Mean consensus fails with even a single malicious robot; its breakdown point is zero.
Median consensus tolerates corruption of fewer than half the neighborhood, ignoring outliers entirely.
Trimmed mean balances the median's robustness against the mean's resolution.
Provable Byzantine agreement needs more than two-thirds honest agents: a hard limit, not a tuning knob.

There is something quietly profound here. The robust swarm never identifies its traitor, never accuses anyone, never even asks who lied. It simply structures its decision so that no single liar can matter, and then proceeds, unbothered, toward the truth.

That same idea, scaled to a planet, is what keeps a blockchain honest: Byzantine fault tolerance running across thousands of strangers, none of whom trust each other, all of whom agree anyway. The deepest robustness isn't catching the liar. It's making the lie powerless.