Speaker: Rotem Oshman, MIT
Title: The Communication Complexity of Aggregating Data in Directed Networks
Abstract:
Computing functions of data scattered across a large, decentralized network is a basic buildingblock in distributed computing. The problem is wellstudied in networks with bidirectional communication links; it is known that in that setting the time complexity of many useful functions (e.g., sum, minimum, and kth order statistic) is dominated by the diameter D of the network. Most algorithms for undirected networks first build a spanning tree in O(D) rounds, and then use it to compute the function.
In this work we study data aggregation in wireless adhoc networks. Because of interference, noise, and differing transmission powers, such networks are often not symmetric; we show that unlike the symmetric case, in directed wireless networks the round complexity of several classical aggregation problems is polynomial in the size of the network, even when the diameter is constant. For example, if messages are restricted to B bits and the diameter is 2, computing an epsilonapproximate count requires \Omega(min {n,1/epsilon2} / B) rounds, and finding the minimum data value takes \Omega(\sqrt{n/B}) rounds. Moreover, for oneshot problems it is not optimal to build a spanning tree, because finding a rooted tree requires \Omega(n/B) rounds , even when the diameter is 2. To prove these results we use several lower bounds in communication complexity, including the recent lower bound of Chakrabarti and Regev on the communication complexity of Gap Hamming Distance.
