Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Berman et al. [75] <s> Broadcasting is a process of transmitting a message held in one node of a communication network to all other nodes. Links of the network are subject to randomly and independently distributed faults with probability0 <s> BIB001 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Berman et al. [75] <s> Fault-tolerant broadcasting in the message passing and radio models is considered under a probabilistic failure model. At each step, the transmitter of each node may fail with fixed constant probability p<1, and failures are independent. Both node-omission and malicious transmission failures are studied. Our goal is to establish conditions on feasibility and to estimate the (synchronous) time complexity of almost-safe broadcasting (i.e., broadcasting which is correct with probability at least 1-1/n for n-node graphs and for sufficiently large n) under these scenarios. If only node-omission failures are assumed, almost-safe broadcasting is feasible for any p<1, in both communication models. For malicious transmission failures, almost-safe broadcasting in the message passing model is feasible iff p<1/2, and in the radio model it is feasible iff p<(1-p)^@D^+^1, where @D is the maximum degree of the network. For the time complexity of almost-safe broadcasting, a number of upper and lower bounds are given in the various models. <s> BIB002
In a single-hop network, consider the case where each node suffers a Byzantine fault with constant probability p < 1/2; recall, this is the probabilistic fault scenario. Can reliable broadcast be achieved? And if so, what is the latency? These are the questions addressed by Berman et al. BIB001 who show that reliable broadcast can be achieved with probability at least (1 − 1/n) and with a latency of O(log n) where n is the number of nodes. The broadcast protocol is framed as follows. All nodes are partitioned into Θ(n/ log n) groups each of size Θ(log n). These groups are then viewed as nodes belonging to a binary tree. The root node signifies the initial point of broadcast of the message where each node in this root group accepts the source's broadcast. Then, at each step, the message propagates along the edges of the tree to the children. The method of propagation involves the use of expander graphs. Specifically, communication from a parent group G 1 to a child group G 2 occurs along the edges of a bipartite expander graph defined in  . Each node then majority filters on the incoming messages in order to obtain the correct messages. The properties of the expander graph ensure that, given a constant probability of failure p < 1/2, a majority of the nodes in the child group will commit to the correct message with probability at least 1 − 1/n. This propagation occurs from the root to the leaf level of the logical binary tree. At this point, the following action is taken by each node in each group in parallel. A node transmits its decision to other nodes within its group through the use of edge-disjoint matchings that together cover all edges corresponding to the group's complete graph on m nodes. This group action allows for the presence of erroneous messages to be "washed out" and, therefore, all correct nodes will have the correct message with high probability. The broadcast at the root requires O(log n) time and each transmission from parent group to child group requires O(1) time. Therefore, propagation to the leaf level requires O(log n) time. Finally, the group action requires O(log n) time per group; however, as it is run in parallel, the total running time of the broadcast protocol is O(log n). The approach of using groups of size Θ(log n) is what allows for the high-probability guarantees of this work. Note that, if the probability of a Byzantine fault is at least 1/2, broadcast is guaranteed to fail with high probability by application of simple Chernoff bounds. While the main results of Berman et al. are given in the context of complete graphs, their algorithm can be applied to multi-hop networks assuming that the topology supports it. For instance, the authors suggest a tree topology where the nodes of the tree represent cliques of, say, logarithmic size and each group has all-to-all links with any children groups. However, such topologies seem somewhat restrictive and it is unclear whether such an algorithm would find utility outside of single-hop networks. BIB002 Like the previous work, here Pelc and Peleg [77] consider the probabilistic fault scenario, reliable broadcast occurs logically along a tree topology rooted at the source, and success is guaranteed with high probability. However, in contrast to the previous work where failures were permanent, the failures here are assumed to be transient; that is, they occur for a single step and then may be corrected. A substantial portion of this work focuses on a message passing model where a node may send (possibly different) messages to each of its neighbors simultaneously and it may receive messages from all of its neighbors simultaneously. For the purposes of this survey, we focus on the results derived for the radio model which is a suitable fit for communications in a sensor network.