## 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.