Bounds on Topology Discovery in the Presence of Byzantine Faults
Mikhail Nesterenko, Inria Grand Large · 2006
This report is a companion to another technical report (3) to present the formal proofs that could not t into the conference proceed- ings of this article (4) due to space limitations. In this report we revisit the problem of Byzantine-robust topology discovery. We formally state the weak and strong versions of the problem. We focus on non-cryptographic solutions to these problems and explore their bounds. We prove that the weak topology discovery problem is solvable only if the connectivity of the network exceeds the number of faults in the system. Similarly, we show that the strong version of the problem is solvable only if the network connectivity is more than twice the number of faults.