### Preview

### Description

*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.