Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Pelc and Peleg [87] <s> Much work has focused on the Byzantine Generals (or secure broadcast) problem in the standard model in which pairwise communication is available between all parties in the network. Some research has also explored the problem when pairwise channels exist only between selected pairs of players, or under the assumption of "k-cast channels" shared by all subsets of players of size k. However, none of these models are appropriate for radio networks in which a player can communicate only by multicasting a message which is then received by all players within some radius r (i.e., the neighbors of the transmitting node). Yet, as far as we are aware, obtaining secure broadcast in radio networks in the presence of a Byzantine adversary has not been studied before.This paper corrects this omission, and provides the first analysis of secure broadcast in radio networks for the case of Byzantine adversaries. We note that secure broadcast is impossible in the presence of an omnipotent adversary. To bypass this barrier, we make the following assumption: there exists a prefixed schedule for players to communicate and everyone (including corrupted ones) adheres to this schedule. Under this assumption, we give a simple broadcast protocol which is provably secure whenever the adversary corrupts at most 1 4 r(r+√rover2 + 1)-3 neighbors (roughly a 1/4π fraction) of any honest player. On the other hand, we show that it is impossible to achieve secure broadcast when the adversary corrupts ⌈1/2 r(2r+1)⌉ (roughly a 1/π fraction) neighbors of any honest player. <s> BIB001 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Pelc and Peleg [87] <s> We consider the problem of reliable broadcast in an infinite grid (or finite toroidal) radio network under Byzantine and crash-stop failures. We present bounds on the maximum number of failures that may occur in any given neighborhood without rendering reliable broadcast impossible. We improve on previously proved bounds for the number of tolerable Byzantine faults [6]. Our results indicate that it is possible to achieve reliable broadcast if slightly less than one fourth fraction of nodes in any neighborhood are faulty, and impossible otherwise. We also show that reliable broadcast is achievable with crash-stop failures if slightly less than half the nodes in any given neighborhood may be faulty. In particular, we establish exact thresholds under a specific distance metric. <s> BIB002 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Pelc and Peleg [87] <s> This paper deals with broadcasting in a network with t-locally bounded Byzantine faults. One of the simplest broadcasting algorithms under Byzantine failures is referred to as a certified propagation algorithm (CPA), which is the only algorithm we know that does not use any global knowledge of the network topology. Hence, it is worth focusing on a graph-theoretic parameter such that CPA will work correctly. Using the theory of maximum adjacency (MA) ordering, a new graph-theoretic parameter for CPA is proposed. Within a factor of two, this parameter approximates the largest t such that CPA works for t-locally bounded Byzantine faults. <s> BIB003
Pelc and Peleg examine a generalization of the t-locally bounded fault model; that is, where each node contains at most t Byzantine nodes within its neighborhood. Specifically, they examine the broadcast protocol of Koo BIB001 , which the authors label here as the Certified Propagation Algorithm (CPA), with the aim of establishing conditions for which CPA achieves reliable broadcast under arbitrary graphs in contrast to the grid model. The authors first define X(v, s) to be the number of nodes in v s neighborhood that are closer to s than v and then define the parameter The first main result that the authors present is that, for any graph G such that t < X(G)/2, CPA achieves reliable broadcast. It is interesting to contrast this upper bound against the upper bound of t < (r/2)(r + r/2 + 1) obtained in BIB001 . For example, Figure 1 illustrates a case where only r 2 nodes in N (v) are closer to s. In this case, the bound by Pelc and Peleg gives t < r 2 /2 which is a weaker bound than that given by BIB001 . The authors then turn to lower bounds in arbitrary graphs. To this end, they define a t-local pair cut to be a cut C ⊆ V such that C can be partitioned into two disjoint sets C = C 1 ∪ C 2 such that C 1 and C 2 have the property of being t-locally bounded. Then, the local pair connectivity of a graph G, denoted by LP C(G), is the smallest nonnegative t such that G possesses a t-local pair cut. The lower bound follows: for any graph G, reliable broadcast is infeasible for t ≥ LP C(G). For instance, the authors provide an example with the cube H 3 depicted in Figure 2 . Here, C = {001, 011, 100, 110} partitions H 3 , and C 1 = {001, 011} and C 2 = {100, 110} are both 1-locally bounded; therefore, there is no reliable broadcast protocol for H 3 . Interestingly, it can be shown that there are graphs for which CPA fails to achieve broadcast while another protocol called the Relaxed Propagation Algorithm (RPA) succeeds. With RPA, a node broadcasts a received message immediately after it is heard, along with the entire sequence of nodes through which the message previously passed. A message m is accepted if it was received from: (1) the source directly or (2) t + 1 distinct neighbors who committed to m or (3) 2t + 1 distinct neighbors who received it along 2t + 1 nodedisjoint paths originating from 2t + 1 distinct nodes who committed to m. As we will see, RPA shares features in common with the improved reliable broadcast algorithm of Bhandari and Vaidya BIB002 . In any event, the existence of RPA proves that CPA is not the strongest broadcast protocol. Furthermore, assessing whether reliable broadcast is possible for t ∈ [ X(G)/2 + 1, LP C(G)] is problematic and the authors pose as an open question whether it is possible to tighten this interval by employing a different graph parameter. Finally, the authors examine how knowledge of the graph topology is useful. Specifically, they prove the existence of a graph G for which reliable broadcast is possible when the topology is known, but impossible when the topology is unknown. This result has negative implications for ad hoc networks where devices may self-organize without having global knowledge of the network topology; indeed, the topology may change regularly rather than remaining static. BIB003 In the previous work by Pelc and Peleg  , for an arbitrary graph G = (V, E), the parameters X(G) and LP C(G) were used to characterize the feasibility of reliable broadcast in the locally-bounded fault scenario using CPA. However, the situation for t ∈ [ X(G)/2 +1, LP C(G)] proved to be problematic. Here, Ichimura and Shigeno succinctly demonstrate two main results. First, they show that calculating LP C(G) is NP-hard and so the utility of LP C(G) is further limited. Second, the authors introduce a new parameterX(G) based on the concept of a maximum adjacency ordering. Since the definition ofX(G) is fairly involved, we omit it here and refer the interested reader to the paper. However, using this new parameter, the authors show that CPA achieves reliable broadcast for t <X(G)/2 and cannot when t >X(G). Importantly, it is also shown thatX(G) can be computed efficiently and thatX(G) ≥ X(G) for any graph G. On the other hand, no relationship is established betweenX(G) and LP C(G), so a direct comparison in terms of the relative sharpness of these two parameters is not possible. Nonetheless, this parameter provides an interesting measure for achieving reliable broadcast using CPA; specifically, the range of uncertainty is t ∈ [ X (G/2) + 1, X (G)]. BIB002 ,  The last two works we surveyed, looked at generalizations of the problem posed by Koo BIB001 by investigating arbitrary graph topologies and examining the conditions under which CPA achieved reliable broadcast. Here, the work of Bhandari and Vaidya BIB002 returns to the original grid model and improves over the results of Koo BIB001 and an intermediate result by Vaikuntanathan [90] which lowered the upper bound to t < (