The Taub Faculty of Computer Science Events and Talks

The advent of large-scale wireless networks has presented the distributed computing community with a new challenge: wireless networks are much more disorderly than traditional wired networks, and they are difficult to model and predict. In addition, they are subject to different design considerations: among other criteria, it is crucial to conserve power by reducing the amount of communication between network nodes. This communication constraint leads to interesting connections between distributed computing and communication complexity.

In this talk I will discuss the problem of computing some function of inputs to the nodes of the network (e.g., the average temperature measured in the network, the number of targets tracked, etc.). In traditional, wired networks, this class of problems is "solved": the optimal solution is to compute a spanning tree, then compute the function "up the tree". However, I will show that in wireless networks, finding a spanning tree is much harder, and consequently we are better off finding other ways to compute the function of interest.

To argue that finding a spanning tree is hard, I will introduce a new communication complexity problem called PARTITION, and prove a lower bound on its two-player communication complexity. I will then discuss the relationship to finding a spanning tree, and also describe a fast multi-player algorithm for PARTITION. I will conclude the talk by describing recent work on a new model of communication complexity, aimed to more closely capture the nature of communication in a wireless network.