Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Awerbuch et al. [57] <s> How efficiently can a malicious device disrupt communication in a wireless network? Imagine a basic game involving two honest players, Alice and Bob, who want to exchange information, and an adversary, Collin, who can disrupt communication using a limited budget of β broadcasts. How long can Collin delay Alice and Bob from communicating? In fact, the trials and tribulations of Alice and Bob capture the fundamental difficulty shared by several n–player problems, including reliable broadcast, leader election, static k–selection, and t–resilient consensus. We provide round complexity lower bounds—and (nearly) tight upper bounds—for each of those problems. These results imply bounds on adversarial efficiency, which we analyze in terms of jamming gain and disruption–free complexity. <s> BIB001 </s> Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference <s> Awerbuch et al. [57] <s> In this paper we consider the problem of designing a medium access control (MAC) protocol for single-hop wireless networks that is provably robust against adaptive adversarial jamming. The wireless network consists of a set of honest and reliable nodes that are within the transmission range of each other. In addition to these nodes there is an adversary. The adversary may know the protocol and its entire history and use this knowledge to jam the wireless channel at will at any time. It is allowed to jam a (1-epsilon)-fraction of the time steps, for an arbitrary constant epsilon>0, but it has to make a jamming decision before it knows the actions of the nodes at the current step. The nodes cannot distinguish between the adversarial jamming or a collision of two or more messages that are sent at the same time. We demonstrate, for the first time, that there is a local-control MAC protocol requiring only very limited knowledge about the adversary and the network that achieves a constant throughput for the non-jammed time steps under any adversarial strategy above. We also show that our protocol is very energy efficient and that it can be extended to obtain a robust and efficient protocol for leader election and the fair use of the wireless channel. <s> BIB002
Many of the models surveyed in this paper have a parameter that is associated with limitations on the jamming power of the adversary. For instance, we just witnessed in BIB001 that the value β represented a finite budget which might be interpreted as the duration for which an adversary can behave badly without being detected. In their model, Awerbuch et al. BIB002 constrain the adversary in a different fashion. For any T ∈ N and any window of time w ≥ T , a (T, λ)-bounded adversary is defined as one which can jam at most λw time steps in that window. This type of adversary models so-called bursty jamming. The particular adversary considered here is (T, 1 − )-bounded where > 0 is an arbtrary constant that is unknown to the nodes. This lack of knowledge regarding the jamming duration of the adversary is in line with many other works we survey. However, nodes are assumed to possess very loose estimates of T and the number of nodes n. The adversary is assumed to be adaptive, but non-reactive. That is, the adversary is assumed to know the entire history of the network and may use this information to plan its attacks; however, in any time slot, the adversary makes its decision about whether to jam without any knowledge of actions by the nodes. While there are no Byzantine faults (or any fail-stop faults) in the system, the adversary is assumed to have knowledge of any communication protocol used by the nodes. Collision detection is available to the nodes; however, it is not possible to discern whether the collision is due to malicious interference or due to legitimate transmissions by the nodes. A Robust MAC Protocol: Here, the MAC protocol coordinates access by the nodes to a single shared channel in a time-slotted network. The authors focus on devising a MAC protocol for a single-hop network that utilizes at least a c-fraction of the unjammed time steps for communication amongst the nodes; such a protocol is called c-competitive. Consider the following simple protocol which is used by the authors to illustrate the motivation behind their work. Let node v send a message in each time step with probability p v with p v ≤p for a small constant 0 <p < 1 and let p = v p v . Let an idle time slot be a time slot where the channel is unused (and unjammed) and let a single-message time slot be a time slot where exactly one node uses the channel to broadcast a message. Let q 0 and q 1 be the probability of an idle time slot and a single-message time slot, respectively. The authors show Letting γ = O(1/(log T + log log n)), the authors prove that these simple rules give rise to a MAC protocol that is constant competitive with high probability if executed for Ω( 1 log N max{T, 1 (log 3 N )(log T + log log n) 2 }) time slots where the constant = Ω(1/ log 3 N ) and N = max{T, n}.