Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Bhandari and Vaidya <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> Bhandari and Vaidya <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
The presentation given in BIB002 is intricate and based on a complicated inductive argument which requires careful attention to the geometry of the grid. A much simplified and more elegant presentation was provided subsequently in a technical report  and for ease of exposition, we review this result. Regardless of the presentation, the main result achieved by Bhandari and Vaidya is an improved upper bound that matches the lower bound given by Koo BIB001 . Reliable Broadcast Tolerating Byzantine Faults: The presentation in  is particularly pleasant because, although it applies to the grid, the analysis itself allows us to leave behind the rigid grid layout of the previous work and consider a graph G = (V, E) of arbitrary topology. Here, vertices correspond to nodes/players and an edge (u 1 , u 2 ) implies u 1 ∈ N (u 2 ) and vice versa. An d-cut is a cut C = (S, V − S) containing the dealer d and this cut will be used to represent the frontier of broadcast. The set S, which we will refer to as the source side of the cut, denotes those nodes which have committed to the correct value v and the set V − S denotes those nodes that have not committed. The problem of whether a correct node in V − S will commit to the correct v can be viewed as a connectivity problem. If a node p has a sufficient number of vertex disjoint paths to nodes in S, then p will be able to cross over to the source side of the cut; that is, p will commit correctly. It remains to be seen what number of vertex disjoint paths is sufficient. We briefly review the completeness argument given in  as it is a fairly intuitive but important result that serves as a foundation for several other works we survey later on. Let p(x, y) denote the node p at location (x, y) in the grid. P N(p) of p(a, b) is defined as  P N(p) = N (a+1, b)∪N (a−1, b)∪N (a, b+1)∪N (a, b−1) . The following protocol for reliable broadcast in the presence of Byzantine faults is by Bhandari and Vaidya  . In this protocol, the message COMMIT(i, v) signifies that node i has committed to value v, and the message HEARD(j, i, v) signifies that node j has heard a message COMMIT(i, v). , 2005) • Initially, the source s does a local broadcast of v. Probabilistic Failures: As the authors are examining a model of random failures, the derived results are presented with probabilistic guarantees. In particular, reliable broadcast is asymptotically achievable if P r[reliable broadcast succeeds] → 1 as n → ∞; alternatively, reliable broadcast is said to occur with high probability (w.h.p.). The first major result is that p max < 1/2 is necessary and, letting d min = O(1) denote the minimum node degree, ). The second major result is the existence of a lower bound on the critical degree. The result centers around the simple observation that, if a correct node p has a neighborhood containing at least a 1/2-fraction of faulty nodes, then p will commit to an incorrect value with probability at least 1/2. By leveraging this observation, the authors prove that reliable broadcast is not asymptotically achievable unless the node degree is Ω( ln n ln ). Therefore, the critical degree is d critical = Θ( ln n ln ).