### Lakshminarayanan Subramanian, Randy H. Katz, Volker Roth, Scott Shenker and Ion Stoica

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/CSD-04-1358

2004

### http://www2.eecs.berkeley.edu/Pubs/TechRpts/2004/CSD-04-1358.pdf

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.

BibTeX citation:

@techreport{Subramanian:CSD-04-1358, Author = {Subramanian, Lakshminarayanan and Katz, Randy H. and Roth, Volker and Shenker, Scott and Stoica, Ion}, Title = {Reliable Broadcase in Unknown Fixed-Identity Networks}, Institution = {EECS Department, University of California, Berkeley}, Year = {2004}, URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2004/6505.html}, Number = {UCB/CSD-04-1358}, 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 <i>G</i> connecting <i>n</i> 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 <i>k</i> among the <i>n</i> nodes act in an adversarial manner and the remaining <i>n</i>-<i>k</i> are good nodes. Under what constraints does there exist a distributed algorithm <i>Gamma</i> that enables every good node <i>v</i> to reliably broadcast a message <i>m</i>(<i>v</i>) to all other good nodes in <i>G</i>? While good nodes follow the algorithm <i>Gamma</i>, an adversary can additionally discard messages, generate spurious messages or collude with other adversaries. <p> In this paper, we prove two results on this problem. First, we provide a distributed algorithm <i>Gamma</i> that can achieve reliable broadcast in an unknown fixed-identity network in the presence of <i>k</i> adversaries if <i>G</i> is <i>2k</i> + 1 vertex connected. Additionally, a minimum vertex connectivity of <i>2k</i> + 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., <i>k</i> = 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 <i>G</i>(<i>n</i>, alpha), a single adversary can partition at most <i>O</i>(<i>n</i>^1/alpha * (log <i>n</i>)^(5-alpha)/(3-alpha)) good nodes from the remaining set of good nodes. <p> 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 <i>G</i> 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.} }

EndNote citation:

%0 Report %A Subramanian, Lakshminarayanan %A Katz, Randy H. %A Roth, Volker %A Shenker, Scott %A Stoica, Ion %T Reliable Broadcase in Unknown Fixed-Identity Networks %I EECS Department, University of California, Berkeley %D 2004 %@ UCB/CSD-04-1358 %U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2004/6505.html %F Subramanian:CSD-04-1358