Foundations and Trends® in Networking > Vol 3 > Issue 1

Gossip Algorithms

By Devavrat Shah, Massachusetts Institute of Technology, USA, devavrat@mit.edu

 
Suggested Citation
Devavrat Shah (2009), "Gossip Algorithms", Foundations and Trends® in Networking: Vol. 3: No. 1, pp 1-125. http://dx.doi.org/10.1561/1300000014

Publication Date: 02 Jun 2009
© 2009 D. Shah
 
Subjects
Modeling and Analysis
 

Free Preview:

Download extract

Share

Download article
In this article:
1 Introduction 
2 Preliminaries 
3 Information Dissemination 
4 Linear Computation 
5 Separable Function Computation 
6 Network Scheduling 
7 Network Convex Optimization 
8 Conclusions 
Acknowledgments 
Notations and Acronyms 
References 

Abstract

Unlike the Telephone network or the Internet, many of the next generation networks are not engineered for the purpose of providing efficient communication between various networked entities. Examples abound: sensor networks, peer-to-peer networks, mobile networks of vehicles and social networks. Indeed, these emerging networks do require algorithms for communication, computation, or merely spreading information. For example, estimation algorithms in sensor networks, broadcasting news through a peer-to-peer network, or viral advertising in a social network. These networks lack infrastructure; they exhibit unpredictable dynamics and they face stringent resource constraints. Therefore, algorithms operating within them need to be extremely simple, distributed, robust against networks dynamics, and efficient in resource utilization.

Gossip algorithms, as the name suggests, are built upon a gossip or rumor style unreliable, asynchronous information exchange protocol. Due to their immense simplicity and wide applicability, this class of algorithms has emerged as a canonical architectural solution for the next generation networks. This has led to exciting recent progress to understand the applicability as well as limitations of the Gossip algorithms. In this review, we provide a systematic survey of many of these recent results on Gossip network algorithms. The algorithmic results described here utilize interdisciplinary tools from Markov chain theory, Optimization, Percolation, Random graphs, Spectral graph theory, and Coding.

DOI:10.1561/1300000014
ISBN: 978-1-60198-236-0
132 pp. $90.00
Buy book (pb)
 
ISBN: 978-1-60198-237-7
132 pp. $100.00
Buy E-book (.pdf)
Table of contents:
1: Introduction
2: Preliminaries
3: Information dissemination
4: Linear computation
5: Separable function computation
6: Network scheduling
7: Network convex optimization
Conclusions
Acknowledgements
Notations and Acronyms
References

Gossip Algorithms

Gossip network algorithms, as the name suggests, are built upon a gossip or rumor style unreliable, asynchronous information exchange protocol. They provide algorithmic architecture of choice for many of the emerging networks – such as sensor networks, peer-to-peer networks, social networks and mobile networks of vehicles – that are primarily not designed for, but required to perform communication and computation. Examples include, estimation algorithms in sensor networks, broadcasting news through a peer-to-peer network, or viral advertising in a social network. Gossip algorithms captures the recent excitement in this interdisciplinary topic that is witnessed across the fields of communication, computation, control, signal processing and algorithms.

 
NET-014