Toronto Networking Seminar

Organized by Department of Computer Science and Department of Electrical and Computer Engineering, University of Toronto

Distributed Computation in Sensor Networks via Gossip : Faster Algorithms and a Signal Processing Application

Michael Rabbat
Department of Electrical and Computer Engineering
McGill Unviersity


Friday, April 9, 2pm
Location: BAB024 (Bahen Centre Basement)


Gossip algorithms are an attractive paradigm for distributed computation in sensor networks for a number of reasons including: they run asynchronously, they do not require overhead to establish or maintain routing tables, and they are not susceptible to bottlenecks or single points of failure. Nodes iteratively exchange information with their immediate neighbors until the entire network reaches a consensus on the value being computed. Of course, robustness and autonomy come at a price. For network topologies typically used to model connectivity in wireless networks, such as grids and random geometric graphs, the average number of messages transmitted by each node grows linearly with the size of the network, and hence does not scale. In wireless sensor networks this is especially detrimental since each transmission consumes valuable bandwidth and energy resources. In this talk I will describe recent work on speeding up gossip algorithms by incorporating a constant amount (just 2 taps) of memory at each node. For grids and random geometric graphs, this reduces the number of messages per node from scaling linear to scaling like the square root of the number of nodes in the network. I will also present an example of how a variant of gossip can be used in a decentralized compression application, where one wishes to adaptively compute the most significant (largest energy) coefficients of a linear transform of distributed data without knowing their indices in advance. These results are based on joint work with Rui Castro, Mark Coates, Boris Oreshkin, and Deniz Ustebay.


Michael Rabbat earned the B.Sc. from the University of Illinois at Urbana-Champaign (2001), the M.Sc. degree from Rice University (2003), and the Ph.D. from the University of Wisconsin–Madison (2006), all in electrical engineering. He is currently an Assistant Professor at McGill University. He was a visiting researcher at Applied Signal Technology, Inc., during the summer of 2003. He received the Best Student Paper award at the 2004 ACM/IEEE Conference on Information Processing in Sensor Networks, Outstanding Student Paper Honorable Mention at the 2006 Conference on Neural Information Processing Systems, and the Harold A. Peterson Thesis Prize. His current research focuses on distributed information processing in sensor networks, network monitoring, and network inference.

Host of Talk:

Jörg Liebeherr (