  We study the problem of Byzantine-robust topology discovery in an arbitrary
asynchronous network. We formally state the weak and strong versions of the
problem. The weak version requires that either each node discovers the topology
of the network or at least one node detects the presence of a faulty node. The
strong version requires that each node discovers the topology regardless of
faults. We focus on non-cryptographic solutions to these problems. We 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. We
present solutions to both versions of the problem. The presented algorithms
match the established graph connectivity bounds. The algorithms do not require
the individual nodes to know either the diameter or the size of the network.
The message complexity of both programs is low polynomial with respect to the
network size. We describe how our solutions can be extended to add the property
of termination, handle topology changes and perform neighborhood discovery.
