IBM Israel Research Seminars

Wireless ad-hoc networks are formed when an ad-hoc collection of devices equipped with wireless communication capabilities happen to be in proximity to each other. Clearly, each pair of such devices whose distance is less than their transmission range can communicate directly with each other. Moreover, if some devices occasionally volunteer to act as forwarders, it is possible to form a multiple hop ad-hoc network. An important distinguishing element of these networks from "standard" networks is that they do not rely on any pre-existing infrastructure or management authority. Moreover, due to mobility, the physical structure of the network is constantly evolving.

Semi-reliable multicast is a basic service for many collaborative applications as it provides nearly reliable dissemination of the same information to many recipients. It ensures that most messages will be received by most of their intended recipients. Yet, implementing semi-reliable multicast in an efficient manner, and in particular over a wireless ad-hoc network, is far from trivial. It involves ensuring that a message is forwarded to all nodes as well as overcoming possible message losses.

Unlike infrastructure-based networks in which routers are usually considered to be trusted entities, in ad-hoc networks routing is performed by the devices themselves. Thus, there is a high risk that some of the nodes of an ad-hoc network will act in Byzantine manner, or in other words, would not respect the networking protocols. This can be a result of maliciousness, or simply selfishness (trying to save their own battery's power). Thus, the possibility of having Byzantine nodes in the system motivates the development of Byzantine tolerant multicast protocols for ad-hoc networks.

In this talk I will present an overlay based Byzantine tolerant multicast protocol for wireless ad-hoc networks. The use of an overlay results in a significant reduction in the number of messages. The protocol overcomes Byzantine failures by combining gossiping of message signatures and failure detectors. These ensure that messages dropped by Byzantine nodes will be detected and retransmitted and that the overlay will eventually consist of enough correct processes to enable message dissemination. An appealing property of the protocol is that it only requires the existence of one correct node in each one-hop neighborhood. The hypothesis behind this protocol is validated using extensive simulations.

Joint work with Roy Friedman and Marc Segal paper in DSN 2005.

About the Speaker
Vadim Drabkin (http://www.cs.technion.ac.il/~dvadim) received his B.A. in Computer Science from the Technion - Israel Institute of Technology, and is currently a graduate student at the same institute. He previously worked in Qualcomm Israel and IBM Research Labs in Haifa, Israel. His interests include Group Communication for Mobile Ad-Hoc Networks, Wireless Computing and Byzantine Failures.