Tutorial 2

[PDF version]

Tutorial Title: Gossip and Message-passing Algorithms for Sensor Networks

Authors/Presenters: Alex Dimakis, Michael Rabbat

Duration: 3 hours

Abstract:

This tutorial will focus on iterative message passing algorithms for sensor networks. At each iteration such algorithms exchange local messages between nodes and perform computations with the goal of computing or optimizing a function. Randomized pair selections are usually called gossiping whereas closely related schemes that simultaneously update all the nodes are usually referred to as average consensus algorithms.

Such gossip and consensus algorithms have attracted the attention of researchers in control, distributed signal processing, and networking for a number of reasons. Arguably the most important one is simplicity: because gossiping only requires that information be exchanged between nodes that communicate directly, there is no overhead involved in establishing or maintaining routes through the network. Moreover, because computation is completely decentralized, gossip algorithms are not prone to the communication or security bottlenecks inherent to networks employing a fusion center. However, these attractive properties come at a price. It is now understood that the standard gossip algorithms have very slow convergence rates in typical sensor network topologies hence and consequently require a large amount of energy for communication.

Over the past five years, much work has gone into understanding the performance of these message- passing schemes, enhancing the convergence rate, computing various classes of functions as well as dealing with other communication problems like quantization and transmission over wireless channels. The aim of this tutorial is to provide a survey of recent work, describing developments leading up to the current state-of-the-art. By the conclusion of the tutorial, attendees will have been exposed to the basic tools used to understand how to design message-passing algorithms, intuitively predict and theoretically analyze their convergence and performance properties. We will describe how different gossip and consensus algorithms have been used to address canonical problems in sensor networks, ranging from sensor localization to distributed compression.

Motivation, target audience, and interest for the EWSN community

This tutorial will draw interest from both theoreticians and practitioners from academia and industry. As seen in the list of papers to be covered, there has been substantial new interest in gossip and distributed consensus algorithms for sensor network applications. We therefore expect several members attending the conference to be interested in this tutorial and we plan to provide insights into open problems and future directions.

Outline: This tutorial will cover the following topics:

• Background and basic schemes: Connections to fundamental work in control theory, machine learning and randomized algorithms; simple gossip algorithms to compute linear functions;
• Applications in sensor networks: Sensor localization; distributed camera networks; sensor data compression; clustering, learning, and maximum likelihood estimation; distributing code updates;
• Fast gossip algorithms: geographic gossip; averaging along random paths; lifting Markov chains and exploiting location information; optimal topologies; filtering, shift registers, and observability;
• Analysis techniques: Connections to Markov chain Monte Carlo (MCMC); convergence analysis through mixing times of Markov chains, spectral methods; the conductance method and the Poincaré inequality;
• Open problems and future work: Quantized transmissions; exploiting the wireless medium; the role of sensor mobility; beyond linear functions – distributed optimization and function computation.

About the authors / presenters:

Alex Dimakis is an Assistant Professor at the Viterbi School of Engineering at the University of Southern California. He has been a faculty member in the Department of Electrical Engineering - Systems since 2009. He received his Ph.D. in 2008 and M.S. degree in 2005 in electrical engineering and computer science, both from the University of California, Berkeley. He obtained the Diploma degree in Electrical and Computer Engineering from the National Technical University of Athens in 2003 and was a postdoctoral scholar at the Center for the Mathematics of Information (CMI) at Caltech during 2008. His research interests include communications, signal processing, and networking, with a current focus on distributed storage, large-scale inference and message passing algorithms.

Michael Rabbat earned the B.Sc. from the University of Illinois at Urbana-Champaign (2001), the M.Sc. from Rice University (2003), and the Ph.D. from the University of Wisconsin-Madison (2006), all in Electrical Engineering. In January, 2007, he joined McGill University as an Assistant Professor in the Department of Electrical and Computer Engineering. Dr. Rabbat teaches and conducts research in the areas of networking, statistical signal processing, and machine learning. His current research is focused on distributed information processing in sensor networks, network monitoring, and inferring the structure of networks from incomplete data.