Publica
Hier finden Sie wissenschaftliche Publikationen aus den FraunhoferInstituten. Reliable broadcast in unknown fixedidentity networks
 Proceedings of the 24th Annual ACM Symposium on Principles of Distributed Computing, PODC 2005 : July 17  20, 2005, Las Vegas New York: ACM Press, 2005 ISBN: 1581139942 pp.342351 
 Symposium on Principles of Distributed Computing ; 24 <2005, Las Vegas, Nev.> 

 English 
 Conference Paper 
 Fraunhofer IGD () 
Abstract
In this paper, we formulate a new theoretical problem, namely the reliable broadcast problem in unknown fixedidentity networks. This problem arises in the context of developing decentralized security mechanisms in a specificclass 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 nk 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 fixedidentity 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 (1connected and 2connected) 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 1connected and 2connected 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 powerlaw 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 realworld 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 fixedidentity networks.