Reaching Consensus about Gossip

Speaker: Prof. P. Thiran Abstract: An increasingly larger number of applications require networks to perform decentralized computations over distributed data. A representative problem of these “in-network processing” tasks is the distributed computation of the average of values present at nodes of a network, known as gossip algorithms. They have received recently significant attention across different communities (networking, algorithms, signal processing, control) because they constitute simple and robust methods for distributed information processing over networks. The first part of the talk is a survey some recent results on real-valued (analog) gossip algorithms. For many topologies that are realistic for wireless sensor networks, the classical nearest-neighbor gossip algorithms are slow, but a variation of these algorithms can be proven to order optimal (cost of O(n) messages for a network of n nodes) for some random geometric graphs. A second improvement, inspired by Uniform Gossip, allows to use uni-directional paths to compute the average, instead of requiring to route the average back and forth along the same path (one way paths are better suited in highly dynamic networks). The second part of the talk is devoted to quantized gossip on arbitrary connected networks. By their nature, quantized algorithms cannot produce a real, analog average, but they can (almost surely) reach consensus on the quantized interval that contains the average, in finite time. (This is a joint work with Florence Benezit, Martin Vetterli, Alex Dimakis, Vincent Blondel and John Tsitsiklis.)

You can listen to Reaching Consensus about Gossip online on Radio and Podcast. Open the player on this page to stream the available audio.

Reaching Consensus about Gossip is an episode from Hamilton Institute Seminars (HD / large) by Hamilton Institute.

This episode is 1:12:03 long.

This episode was published on May 27, 2012.

Yes. Use the heart button on the episode page to add it to your favorite episodes list.

Yes. This page shows related episodes from Hamilton Institute Seminars (HD / large) when more episodes are available from the podcast feed.