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. To read.
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?
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.