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)


Abstract:




  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.

 



Bio:



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 (jorg@comm.toronto.edu)