EPISODE · May 27, 2012 · 1H 12M
Reaching Consensus about Gossip
from Hamilton Institute Seminars (HD / large) · host Hamilton Institute
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.)
What this episode covers
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.)
NOW PLAYING
Reaching Consensus about Gossip
No transcript for this episode yet
Similar Episodes
May 31, 2026 ·25m
May 31, 2026 ·30m
May 31, 2026 ·57m
May 31, 2026 ·32m
May 31, 2026 ·29m
May 31, 2026 ·37m