Search
 New @ Now
Products
 FnTs in Business  FnTs in Technology
For Authors
 Review Updates
 Authors Advantages
 Download Style Files
 Submit an article
 

Gossip Algorithms



Author(s): Devavrat Shah

Source:
    Journal:Foundations and Trends® in Networking
    ISSN Print:1554-057X,  ISSN Online:1554-0588
    Publisher:Now Publishers
    Volume 3 Number 1,
Pages: 125(1-125)
DOI: 10.1561/1300000014

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.