Discovering Network Topology in the Presence of Byzantine Faults

Details Discovering Network Topology in the Presence of Byzantine Faults Discovering Network Topology in the Presence of Byzantine Faults

2006-11-22

arxiv.org/abs/cs/0611116v1

13th Colloquium on Structural Information and Communication Complexity (SIROCCO), LNCS Volume 4056 pp. 212-226, Chester, UK, J

Computer Science

Distributed, Parallel, and Cluster Computing

Scientific paper

10.1007/11780823_17

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.

Affiliated with

Also associated with

No associations

Rating

Discovering Network Topology in the Presence of Byzantine Faults does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Discovering Network Topology in the Presence of Byzantine Faults, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Discovering Network Topology in the Presence of Byzantine Faults will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-368336