### Reliable Broadcase in Unknown Fixed-Identity Networks

**Authors:**

Subramanian, Lakshminarayanan

Katz, Randy H.

Roth, Volker

Shenker, Scott

Stoica, Ion
**Technical Report Identifier:** CSD-04-1358
**2004**

CSD-04-1358.pdf

**Abstract:** 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 *Gamma* 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 *Gamma*, 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 *Gamma* 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*, alpha), a single adversary can partition at most *O*(*n*^1/alpha * (log *n*)^(5-alpha)/(3-alpha)) 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 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.