Abstract
As communication networks grow in size, they become increasingly vulnerable to component failures. These networks consist of numerous interacting entities (agents). Since distributed systems have become popular and widely used in contemporary networking, the provided solutions need to cope with erroneous and malicious components in the underlying communication network. Security and reliability issues that arise have been objects of extensive research in the fields of Secure Multiparty Computations and Distributed Computing. In our work we contribute to the realization of fundamental communication primitives (Reliable Broadcast and Reliable Message Transmission) in an adversarial distributed environment, by investigating the impact of the network structure and the agents' topology knowledge level on the achievability of these tasks. We consider a worst-case (Byzantine) adversary, which makes the agents misbehave arbitrarily,Initially, we consider the t-locally bounded adversary model, i ...
As communication networks grow in size, they become increasingly vulnerable to component failures. These networks consist of numerous interacting entities (agents). Since distributed systems have become popular and widely used in contemporary networking, the provided solutions need to cope with erroneous and malicious components in the underlying communication network. Security and reliability issues that arise have been objects of extensive research in the fields of Secure Multiparty Computations and Distributed Computing. In our work we contribute to the realization of fundamental communication primitives (Reliable Broadcast and Reliable Message Transmission) in an adversarial distributed environment, by investigating the impact of the network structure and the agents' topology knowledge level on the achievability of these tasks. We consider a worst-case (Byzantine) adversary, which makes the agents misbehave arbitrarily,Initially, we consider the t-locally bounded adversary model, introduced in 2004 by Koo, where a fixed upper bound on the number of corruptions in each agent's neighborhood is imposed. We explore the tradeoff between the level of topology knowledge and the solvability of the problem by developing a versatile technique which allows us to obtain impossibility results for every level of topology knowledge. Checking the necessary conditions for the solvability of the problem proves to be NP-hard but along the way we obtain an efficient 2-approximation algorithm for the ad hoc case (where agents only know their local neighborhood). On the positive, we generalize the algorithmic idea behind the simple, yet powerful Certified Propagation Algorithm (CPA), also introduced by Koo in 2004, and propose algorithms, that match the obtained bounds (unique algorithms) in every case. Thus, we exactly characterize the classes of graphs in which reliable communication is possible with respect to topology knowledge. In order to achieve these we introduced the Partial Knowledge Model in which each agent knows a part of the network, namely a connected subgraph containing itself. As a part of the latter contribution, we manage to settle an open question of Pelc and Peleg (2005) in the affirmative, by showing that in ad hoc networks, CPA is unique, that is, it can tolerate as many local corruptions as any other Broadcast algorithm.Furthermore, we manage to generalize our results in the General Adversary model of Hirt and Maurer (1997), which subsumes earlier models by adapting our techniques and algorithms from the t-locally bounded model. Thus, we devise the first optimally resilient algorithms for Reliable Broadcast/Message transmission under restricted knowledge and general adversaries. We also study the efficiency of RMT protocols by introducing an algorithmic property which implies that a protocol scheme is as efficient as any other for a certain problem with respect to polynomial time. To obtain our latter results we employ, among others, a novel notion of joining operation on adversary structures, appropriate notions of separators in unreliable networks, and a self-reducibility property of the RMT problem.Finally, we study energy-efficient Broadcast in wireless networks, where simultaneous transmissions lead to signal interference which prevents message propagation. In particular, we examine the $k$-shot wireless network model, in which a bound k on the number of transmissions for every player is given. We prove a lower bound on the Broadcast time of any protocol.
show more
