A Byzantine node can behave arbitrarily: lie, tell different neighbours different things, go silent, or behave correctly until later. The name comes from Lamport, Shostak and Pease’s 1982 paper about generals agreeing on a plan when some of them are traitors.
The classic bound for exact agreement: with nodes you can tolerate at most traitors if .
Relevance to robots
Hacked firmware, spoofed GPS, and a failed sensor that still reports plausible numbers look the same from the outside. A compromised PLC in a water treatment plant is also a Byzantine node (see cyber-physical security).
Faults and attacks
Most robotics papers don’t separate a faulty teammate from a malicious one. Fault papers assume random, independent faults. Security papers assume a bounded number of worst-case robots with trusted identities (Wardega, Strobel). A real robot with its own identity and a broken sensor falls through both, and the two cases call for different responses: repair it, or cut it off. More in failure recovery.
Physical witnesses help. Gil and others use Wi-Fi fingerprints a spoofer can’t forge, SABER caps an agent’s trust by its worst report, and RigidShift shows that checking robots only against each other misses a shift of the whole group.
See also
- resilient consensus for agreement on continuous values.
- Byzantine-robust learning for training models when some workers lie.
- Robust estimation: TEASER++ proves exact registration needs at least three more inliers than adversarial outliers, the estimation version of .
- Robust robotics, the thread this belongs to.
References
- L. Lamport, R. Shostak, M. Pease. The Byzantine generals problem. ACM Transactions on Programming Languages and Systems, 1982.