Reliable broadcast in unknown fixed-identity networks

In this paper, we formulate a new theoretical problem, namely the reliable broadcast problem in unknown fixed-identity networks. This problem arises in the context of developing decentralized security mechanisms in a specific-class of distributed systems: Consider an undirected graph G connecting n nodes where each node is aware of only its neighbors but not of the entire graph. Additionally, each node has a unique identity and cannot fake its identity to its neighbors. Assume that k among the n nodes act in an adversarial manner and the remaining n-k are good nodes. Under what constraints does there exist a distributed algorithm T that enables every good node v to reliably broadcast a message m(v) to all other good nodes in G? While good nodes follow the algorithm , an adversary can additionally discard messages, generate spurious messages or collude with other adversaries. In this paper, we prove two results on this problem. First, we provide a distributed algorithm F that can achieve reliable broadcast in an unknown fixed-identity network in the presence of k adversaries if G is 2k+1 vertex connected. Additionally, a minimum vertex connectivity of 2k +1 is a necessary condition for achieving reliable broadcast. Next, we study the problem of reliable broadcast in sparse networks (1-connected and 2-connected) in the presence of a single adversary i.e., k = 1. In sparse networks, we show that a single adversary can partition the good nodes into groups such that nodes within a group can reliably broadcast to each other but nodes across groups cannot. For 1-connected and 2-connected graphs, we prove lower bounds on the number of such groups and provide a distributed algorithm to achieve these lower bounds. We also show that in a power-law random graph G(n, ), a single adversary can partition at most O(n 1/ x (log n) (5-)/(3-)) good nodes from the remaining set of good nodes. Addressing this problem has practical implications to two real-world problems of paramount importance: (a) developing decentralized security measures to protect Internet routing against adversaries; (b) achieving decentralized public key distribution in static networks. Prior works on Byzantine agreement [17, 11, 23, 13, 3, 4, 24] are not applicable for this problem since they assume that either G is known, or that every pair of nodes can directly communicate, or that nodes use a key distribution infrastructure to sign messages. A solution to our problem can be extended to solve the byzantine agreement problem in unknown fixed-identity networks.