Resilient consensus

3 min read

Getting a group to agree on a value (a meeting point, a heading, an estimate) when up to members may be Byzantine.

Plain averaging has no defence: one liar reporting an extreme value can move everyone, because the mean has a breakdown point of zero. The explainer shows this.

W-MSR

Weighted Mean-Subsequence-Reduced. Each normal agent sorts the values it hears, drops up to that are larger than its own and up to that are smaller, and takes a weighted average of what’s left and its own value.

  • Safety: if each agent has at most Byzantine neighbours, normal agents never leave the range spanned by the normal agents’ initial values.
  • Agreement needs the network to be connected enough. LeBlanc, Zhang, Koutsoukos and Sundaram (2013) show that -robustness is sufficient. Robustness asks that for any two disjoint groups, someone in one of them has enough neighbours outside it.
  • The idea goes back to approximate agreement (Dolev, Lynch, Pinter, Stark and Weihl, 1986).

Multi-dimensional values

Applying W-MSR one coordinate at a time keeps agents inside the bounding box of the normal agents, which is weaker than the convex hull. Vector versions exist but cost more. Reputation-based consensus (2026) reaches vector consensus without being told : each agent scores its neighbours from the discrepancies it sees and can push a neighbour’s weight to zero. To read.

In robot teams

  • Strobel and others compare W-MSR with a blockchain approach in a simulated swarm. W-MSR ran on a graph with average degree 2.4, far below the connectivity its guarantee needs, which says more about sparse swarms than about W-MSR.
  • Ballotta and others weight neighbours by trust from a physical-layer signal, which catches spoofed identities and fully trusts a real robot with a broken sensor.
  • The blocklist protocol removes Byzantine robots by accusation, and blocks the honest accuser along with the accused.
  • FRAC-MARL brings the same idea to multi-agent RL when only the links are corrupted.
  • The flocking result underneath much of this is Jadbabaie, Lin and Morse (2003).

Open questions

  • Robot teams move, so the communication graph changes as they coordinate. Which robustness guarantees survive that?
  • Robustness is expensive to check on a large graph. Is there a cheap way for a team to check it?
  • Can the same trimming work on map claims instead of numbers? See 3D scene graphs.

References

  • H. J. LeBlanc, H. Zhang, X. Koutsoukos, S. Sundaram. Resilient asymptotic consensus in robust networks. IEEE Journal on Selected Areas in Communications, 2013.
  • D. Dolev, N. Lynch, S. Pinter, E. Stark, W. Weihl. Reaching approximate agreement in the presence of faults. Journal of the ACM, 1986.