Network gossip algorithms
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. Ind...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers
2011
|
| Online Access: | http://hdl.handle.net/1721.1/61363 https://orcid.org/0000-0003-0737-3259 |
| _version_ | 1826207304587935744 |
|---|---|
| author | Shah, Devavrat |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Shah, Devavrat |
| author_sort | Shah, Devavrat |
| collection | MIT |
| description | 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 network 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 survey, I will discuss some of these recent results on gossip network algorithms. The algorithmic results described here in a natural way bring together tools and techniques from Markov chain theory, optimization, percolation, random graphs, spectral graph theory, and coding. |
| first_indexed | 2024-09-23T13:47:13Z |
| format | Article |
| id | mit-1721.1/61363 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:47:13Z |
| publishDate | 2011 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | mit-1721.1/613632022-09-28T16:11:19Z Network gossip algorithms Shah, Devavrat Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Shah, Devavrat Shah, Devavrat 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 network 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 survey, I will discuss some of these recent results on gossip network algorithms. The algorithmic results described here in a natural way bring together tools and techniques from Markov chain theory, optimization, percolation, random graphs, spectral graph theory, and coding. National Science Foundation (U.S.). Division of Computer and Network Systems National Science Foundation (U.S.). Division of Human and Social Dynamics National Science Foundation (U.S.). Division of Computing and Communication Foundations 2011-03-01T22:23:43Z 2011-03-01T22:23:43Z 2009-04 Article http://purl.org/eprint/type/JournalArticle 978-1-4244-2353-8 1520-6149 INSPEC Accession Number: 10701476 http://hdl.handle.net/1721.1/61363 Shah, D. “Network gossip algorithms.” Acoustics, Speech and Signal Processing, 2009. ICASSP 2009. IEEE International Conference on. 2009. 3673-3676. Copyright © 2009, IEEE https://orcid.org/0000-0003-0737-3259 en_US http://dx.doi.org/10.1109/ICASSP.2009.4960423 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Institute of Electrical and Electronics Engineers SPIE |
| spellingShingle | Shah, Devavrat Network gossip algorithms |
| title | Network gossip algorithms |
| title_full | Network gossip algorithms |
| title_fullStr | Network gossip algorithms |
| title_full_unstemmed | Network gossip algorithms |
| title_short | Network gossip algorithms |
| title_sort | network gossip algorithms |
| url | http://hdl.handle.net/1721.1/61363 https://orcid.org/0000-0003-0737-3259 |
| work_keys_str_mv | AT shahdevavrat networkgossipalgorithms |