Research Abstracts - 2007

Overview

Byzantine adversaries pose a particular threat to radio networks. Due to the shared nature of the communication medium, an adversary can prevent any information exchange between honest processes by jamming the channel with noise. The first attempts to tackle this problem assumed that the malicious adversary could only corrupt honest processes, but not interefere with communication (c.f. [2,4]). Another approach has been to assume that the adversary interferes only in a probabilistic manner, causing either random transient message corruption (c.f. [6]), or random permanent process corruptions (c.f. [1]). More recent work allows malicious interference—but bounds the number of times that the adversary can disrupt communication (c.f. [3,5]).

In this project, we place no such restrictions on the adversary. To compensate, we shift our focus to multi-channel radio networks in which each process, including the adversary, must choose in each round a single channel on which to participate. By transmitting on a given channel at the same time as an honest process, the advesary can prevent this process's message from being received. This setting is appealing because of its practicality. Almost every major commerical/industrial/military radio device—including sensor motes, laptops running 802.11, and bluetooth-enabled devices—has the capability to switch between multiple communication channels.

We assume that honest processes maintain no shared secrets (e.g., information unknown to the adversary). The honest processes could use such information to derive, for example, a transmission pattern that appears random to an outside observer. (Military communication systems, like those used with the MILSTAR satellite system, use such a scheme to evade eaves-droppers). We omit this possibility for two reasons. First, we are interested in deterministic solutions that guarantee correctness even in the worst case. Second, for low-resource devices—such as RFID tags or tiny sensor motes—cryptographic calculations and secure key dissemination may be prohibitively expensive.

With such devices in mind, we focus on oblivious algorithms—those in which a process's decision to transmit or listen in a given round is a function only of its unique identifier, the round number as well as the number of processes and channels in the network. Oblivious algorithms are appealing because they are considered easy to construct and deploy.

We study the fundamental problem of gossip in which processes attempt to exchange values. The problem of disseminating information has been well-studied in single-channel radio networks.

We introduce a a parameterized version of the gossip problem, called x-gossip, in which (1-x)n initial values must be disseminated to at least (n-1) processes. (As we prove, it is impossible to disseminate even a single value to all n receivers in this setting). The x-gossip problem is a generalization of classical all-to-all gossip (0-gossip) that allows for more flexability in the number of values that need to be spread—a desirable feature for many efficiency—concerned applications (e.g., when only a majority vote is needed).

Results

We have shown that Theta(n/xc²) rounds are necessary and sufficient to solve x-gossip, where n is the number of processes and c the number of communication channels. We demonstrate necessity by reducing x-gossip to an abstract combinatorial game-(n,x)-clique destruction-in which a player tries to remove enough edges from an n-clique such that no clique of size greater than xn remains. We then prove a lower bound on this game using a new graph theorem concerning clique size after worst-case graph edge removals.

To demonstrate sufficiency, we describe a deterministic oblivious algorithm that matches the bound. The algorithm proceeds in two phases. During the first phase, a sufficient number of values are disseminated to a distinguished group of listeners distributed among the channels. During the second phase, these values are disseminated to increasingly larger sets of processes until n-1 have learned the total requisite knowledge.

We conclude with two extensions to our solution. The first concerns an adversary that can interfere with more than one channel per round. We indicate that this solution is optimal for certain special cases. The second extension handles a more traditional byzantine adversary that corrupts honest processes, rather than simply disrupting the communication.

Future Work:

There remain a variety of open problems. First, there remains several questions with respect to adversaries that can block more than one channel: Can we develop a more efficient algorithm? Can we extend the clique-destruction technique to show general lower bounds for the multi-channel adversary? Second, we would like to consider the multi-hop case where the players are attempting to disseminate data across a multi-hop network.

Support:

This work is supported in part by NSF Award #CCR-0326277 and USAF, AFRL Award #FA9550-04-1-0121.

References:

[1] V. Bhandari and N. H. Vaidya. Reliable broadcast in wireless networks with probabilistic failures. Technical report, University of Illinois at Urbana-Champaign, January 2007. To appear in InfoCom 2007.

[2] V. Bhandari and N. H. Vaidya. On reliable broadcast in a radio network. In Proceedings of PODC, 2005.

[3] S. Gilbert, R. Guerraoui, and C. Newport. Of malicious motes and suspicious sensors: On the efficiency of malicious interference in wireless networks. In Proceedings of OPODIS, 2006.

[4] C-Y. Koo. Broadcast in radio networks tolerating byzantine adversarial behavior. In Proceedings of PODC, 2004.

[5] C.-Y. Koo, V. Bhandari, J. Katz, and N. H. Vaidya. Reliable broadcast in radio networks: The bounded collision case. In Proceedings of PODC, 2006.

[6] A. Pelc and D. Peleg. Feasibility and complexity of broadcasting with random transmission failures. In Proceedings of PODC 2005.