Lying robots

Sixteen robots are spread across a field and need to meet. There is no leader and no agreed meeting point, and each robot can only hear the robots close to it.

A simple rule: every step, each robot averages its own position with the positions its neighbours report, and moves a little toward that average. Press play.

The robots converge. This is average consensus, and many multi-robot tasks use some version of it: formation control, coverage, shared maps, distributed estimation.

The dashed box marks where the robots started. Each step moves a robot to an average of positions inside the box, so no robot ever leaves it. Call the box the safe zone. Any reasonable meeting point is inside it.

You can drag robots while it runs, and change how far they can hear. If the range is too short, the group splits into clusters that never meet.

One liar§

Now one robot lies. It keeps reporting a position in the top-right corner, wherever it actually is.

The honest robots include the false position in every average, and the whole group drifts out of the safe zone toward a point that doesn’t exist. One liar out of sixteen decides where everyone ends up.

A single extreme value can move an average anywhere. In statistics this is called a breakdown point of zero.¹

Byzantine faults§

This kind of failure is called Byzantine, after a 1982 paper by Lamport, Shostak and Pease about generals who must agree on a plan when some of them are traitors.² A Byzantine robot can report anything. It can lie, tell different neighbours different things, stay silent, or behave normally until later.

In practice this covers hacked firmware, spoofed GPS, and sensors that fail but keep reporting plausible numbers. From the outside these look the same. I worked on the industrial version of this problem, compromised controllers in water treatment plants, for several years.

The question: is there an update rule that keeps the honest robots safe and still lets them agree, without knowing which robots are lying?

The median§

The median ignores extreme values. Sort the values and take the middle one, and a single outlier hardly moves it. Robots can apply it to each coordinate separately: the median of the x positions they hear, then the median of the y positions.

This works well. Try adding more liars, or switch them to random noise. The median has no setting for how many liars to expect, though, and in a small neighbourhood a few liars can still control the middle value.

W-MSR§

W-MSR (weighted mean-subsequence-reduced) adds that setting.³ Choose a number $F$: the most liars any robot might have among its neighbours. Each honest robot, for each coordinate:

1. sorts the values it hears from its neighbours,
2. removes up to $F$ values that are higher than its own, starting with the highest,
3. removes up to $F$ values that are lower than its own, starting with the lowest,
4. averages the remaining values with its own.

The liar’s report is extreme, so it is always removed. Every value that remains lies between values from honest robots, so the honest robots stay in the safe zone. This holds whatever the liars do, as long as no robot has more than $F$ liars within range.

Try more liars than $F$. Then try the two-faced strategy, where each liar tells robots on the left that it is far left and robots on the right that it is far right. With averaging, this splits the group in two. With W-MSR it has no effect, because both reports are extreme.

When W-MSR gets stuck§

Removing values also removes some honest information. On a sparse network, a robot can end up removing the values that would have moved it toward the others.

The robots stay in the safe zone but stop before they agree. Increase the hearing range and they reach agreement. Setting $F$ to zero also gets agreement, but $F = 0$ is plain averaging, so the liar is in control again.

LeBlanc, Zhang, Koutsoukos and Sundaram showed how much connectivity is enough, using a property called robustness. Roughly: for any two separate groups of robots, at least one robot in one of the groups must hear at least $r$ robots outside its own group. If the network is $(2F+1)$-robust, W-MSR reaches agreement.³ This is a stronger requirement than the network simply being connected.

Playground§

All controls are available here. Some things to try:

• Five liars against W-MSR with $F = 1$.
• Turn off Reveal liars and try to find them from the plot.
• Drag a liar into the middle of the group and see whether its position matters.

Research context§

This is a simplified version of problems in my PhD. Real teams of drones and ground robots share more than positions: maps, detections, plans, and the parameters of models they train together. The same trimming idea appears in Byzantine-robust machine learning, where a server averaging gradients from many workers faces the same problem.⁴ When robots move, their network changes as they coordinate, which the results above don’t fully cover. Notes on that are in the research diary.

Bug reports and questions are welcome on the contact page.

Notes

1. The median’s breakdown point is one half: half of the values must be corrupted before the median can be set arbitrarily. No summary of the data does better. ↩

2. L. Lamport, R. Shostak and M. Pease, “The Byzantine generals problem”, ACM Transactions on Programming Languages and Systems, 1982. For exact agreement, they showed that more than three times as many generals as traitors are needed. ↩

3. H. J. LeBlanc, H. Zhang, X. Koutsoukos and S. Sundaram, “Resilient asymptotic consensus in robust networks”, IEEE Journal on Selected Areas in Communications, 2013. These algorithms build on work on approximate agreement by Dolev, Lynch, Pinter, Stark and Weihl (1986). Applying the rule one coordinate at a time, as these robots do, keeps them inside the box of honest starting positions, which is weaker than staying inside their convex hull. ↩ ↩²

4. P. Blanchard, E. M. El Mhamdi, R. Guerraoui and J. Stainer, “Machine learning with adversaries: Byzantine tolerant gradient descent”, NeurIPS 2017; D. Yin, Y. Chen, K. Ramchandran and P. Bartlett, “Byzantine-robust distributed learning: towards optimal statistical rates”, ICML 2018. ↩