Computer Science Colloquium, 2005-2006

Gregory Chockler
IBM Haifa Research Laboratory

Robust Coordination in Wireless Ad Hoc Networks

Ongoing proliferation of radio-equipped devices has inspired new uses for wireless ad hoc networking that extend beyond simple data collection and aggregation (as in sensor networks). In particular, applications such as cooperative control of industrial regulator valves or precision guidance of weapon strikes require ongoing coordination among the wireless peers in an attempt to react consistently to (possibly conflicting) stimuli provided by the environment. The key enabler of such coordination is a distributed agreement protocol that ensures that the nodes presented with conflicting inputs will eventually decide on a single consistent output (which is a function of the inputs).

In this talk, I will present results that shed light on the possibility and inherent limitations of implementing distributed agreement in wireless ad hoc networks. I will consider a variety of the environment and failure assumptions (motivated by real wireless networks), and attempt to give a precise sense as to how they affect the agreement solvability and the solution complexity. I will outline several agreement algorithms, and discuss their performance in practical settings. The proposed algorithms rely on several higher-level programming abstractions that can be of independent interest.

Based on joint work with Murat Demirbas (SUNY Buffalo), Seth Gilbert (MIT) and Calvin Newport (MIT), and papers in PODC 2005, ADSN 2005, and Allerton Conference on Communication, Control, and Computing 2005.

Shuly Wintner
Last modified: Thu Jan 12 09:00:23 IST 2006