  Traditional Byzantine resilient algorithms use 2f+1 vertex disjoint paths to
ensure message delivery in the presence of up to f Byzantine nodes. The
question of how these paths are identified is related to the fundamental
problem of topology discovery. Distributed algorithms for topology discovery
cope with a never ending task, dealing with frequent changes in the network
topology and unpredictable transient faults. Therefore, algorithms for topology
discovery should be self-stabilizing to ensure convergence of the topology
information following any such unpredictable sequence of events. We present the
first such algorithm that can cope with Byzantine nodes. Starting in an
arbitrary global state, and in the presence of f Byzantine nodes, each node is
eventually aware of all the other non-Byzantine nodes and their connecting
communication links. Using the topology information, nodes can, for example,
route messages across the network and deliver messages from one end user to
another. We present the first deterministic, cryptographicassumptions- free,
self-stabilizing, Byzantine-resilient algorithms for network topology discovery
and end-to-end message delivery. We also consider the task of r-neighborhood
discovery for the case in which r and the degree of nodes are bounded by
constants. The use of r-neighborhood discovery facilitates polynomial time,
communication and space solutions for the above tasks. The obtained algorithms
can be used to authenticate parties, in particular during the establishment of
private secrets, thus forming public key schemes that are resistant to
man-in-the-middle attacks of the compromised Byzantine nodes. A polynomial and
efficient end-to-end algorithm that is based on the established private secrets
can be employed in between periodical re-establishments of the secrets.
