Discovering network topology in the presence of Byzantine faults. (English) Zbl 1222.68047
Flocchini, Paola (ed.) et al., Structural information and communication complexity. 13th international colloquium, SIROCCO 2006, Chester, UK, July 2–5, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-35474-1/pbk). Lecture Notes in Computer Science 4056, 212-226 (2006).
Summary: 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. Our solutions match the established graph connectivity bounds. The programs are terminating, they 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.
For the entire collection see [Zbl 1113.68004].
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. Our solutions match the established graph connectivity bounds. The programs are terminating, they 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.
For the entire collection see [Zbl 1113.68004].
MSC:
| 68M15 | Reliability, testing and fault tolerance of networks and computer systems |
| 68M14 | Distributed systems |
