Research Abstracts - 2006

Wireless Broadcast with Byzantine Adversaries

Seth Gilbert, Rachid Guerraoui & Calvin Newport

Abstract

How much damage can a malicious tiny device cause in a single-hop wireless network? Imagine two players, Alice and Bob, who want to exchange information. Collin, a malicious adversary, wants to prevent them from communicating. By broadcasting at the same time as Alice or Bob, Collin can destroy their messages or overwhelm them with his own malicious data. Being a tiny device, however, Collin can only broadcast up to k times. Given that Alice and Bob do not know k, and cannot distinguish honest from malicious messages, how long can Collin prevent them from communicating? We show the answer to be 2k+?(log|V|) communication rounds, where V is the set of values that Alice and Bob may transmit. We prove this result to be optimal by deriving an algorithm that matches our lower bound---even in the stronger case where Alice and Bob do not start the game at the same time.

We then argue that this specific 3-player game captures the general extent to which a malicious adversary can disrupt coordination in a single-hop wireless network. We support this claim by deriving---via reduction from the 3-player game---round complexity lower bounds bounds for several classical n-player problems: 2k + ?(log|V|) for reliable broadcast, 2k + ý(log{n/k}) for leader election among k contenders, and 2k + ý(k log|V|/k) for static k-selection. We then consider an extension of our adversary model that also includes up to t crash failures. We study binary consensus as the archetypal problem for this environment and show a bound of 2k + ?(t) rounds. We conclude by providing tight, or nearly tight, upper bounds for all four problems. The new upper and lower bounds represent the first such results for a wireless network in which the adversary has the ability to disrupt communication.

Introduction

As wireless technology has improved and miniaturized, there has been increasing interest in large-scale, widely-deployed sensor networks. Unfortunately, communication in wireless networks is unreliable: collisions and other wireless interference might cause significant message disruption. Moreover, a small number of malicious "Byzantine" adversaries can easily disrupt protocols by jamming the communication channels with random noise. We ask the fundamental question of how much disruption a malicious (Byzantine) device can cause in such a network. We establish a tight bound for a constrained 3-player game, and then show how this bound implies results for more general n-player problems such as reliable broadcast, leader election, static k-selection and consensus.

Environment

We consider a single-hop wireless radio channel shared by several devices operating in synchronous rounds. If one device broadcasts, then all devices receive its message. If two or more devices broadcast, then each listening device either receives one of the messages or simply detects noise, indicating a collision. The honest devices, which we call players, follow a designated algorithm, and can use various strategies---such as a round-by-round TDMA schedule---to avoid contention on the communication channel. A major novelty of our work is considering, for the first time in the context of wireless networks, malicious devices that can deviate from honest broadcasting behavior. In our model, a malicious device can broadcast in any round, potentially destroying honest messages or overwhelming them with malicious data. As is typically assumed in these networks---due to computational and bandwidth limitations, as well as the challenges of ad hoc deployment---the tiny devices cannot authenticate messages. Therefore, a message sent by a malicious device cannot necessarily be distinguished from one sent by an honest player.

The Game

We first focus on a constrained communication game involving two honest players---Alice and Bob---and one malicious adversary, Collin (the Collider). Alice and Bob are each initially given a value to communicate. Collin, jealous about the state of affairs between Alice and Bob, is determined to prevent them from communicating (in either direction) for as long as possible. A straightforward strategy for Collin is to broadcast a message in every round, systematically provoking a collision whenever another message is sent, thus preventing Alice and Bob from ever exchanging any information.

Being a tiny device, Collin cannot broadcast more than some budget of k messages, where k is a priori unknown to Alice and Bob. This assumption generalizes several examples of limited malicious interference, such as a bounded energy budget.

We then consider the general n-player problems of reliable broadcast, leader election, static k-selection and consensus.

Progress

We show the following bounds: two-player communication: 2k+?(log|V|) rounds; reliable broadcast: 2k+?(log|V|) rounds, leader election among k contenders: 2k + ý(log{n/k}) rounds; static k-selection: 2k + ý(k log|V|/k) rounds. Moreover, if an additional t crash failures are possible, we give a bound of 2k + ?(t) rounds for consensus.

Research Support

This work is supported in part by NSF grant CCR-0098305 and NSF ITR Grant 0121277, AFOSR Contract #F49620-00-1-0097, DARPA Contract #F33615-01-C-1896, NSF Grant 64961-CS, and NTT Grant MIT9904-12.