{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,10]],"date-time":"2026-10-10T11:09:59Z","timestamp":1791630599890,"version":"4.3.4"},"reference-count":70,"publisher":"Emerald","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009,6,2]]},"abstract":"<jats:p>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.<\/jats:p>\n                  <jats:p>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.<\/jats:p>","DOI":"10.1561\/1300000014","type":"journal-article","created":{"date-parts":[[2009,6,25]],"date-time":"2009-06-25T04:47:27Z","timestamp":1245905247000},"page":"1-125","source":"Crossref","is-referenced-by-count":198,"title":["Gossip Algorithms"],"prefix":"10.1108","volume":"3","author":[{"given":"Devavrat","family":"Shah","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology , Cambridge, MA,","place":["USA"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"140","published-online":{"date-parts":[[2009,6,2]]},"reference":[{"key":"2026032901020943500_ref001","doi-asserted-by":"crossref","first-page":"564","DOI":"10.1112\/jlms\/s2-25.3.564","article-title":"Some inequalities for reversible Markov chains","volume":"25","author":"Aldous","year":"1982","journal-title":"Journal of the London Mathematical Society"},{"issue":"4","key":"2026032901020943500_ref002","doi-asserted-by":"crossref","first-page":"429","DOI":"10.24033\/bsmf.1997","article-title":"Plongements lipschitziens dans Rn","volume":"111","author":"Assouad","year":"1983","journal-title":"Bulletin de la Soci\u00b4et\u00b4e Math\u00b4ematique de France"},{"key":"2026032901020943500_ref003","article-title":"Information theoretic approaches to distributed function computation","author":"Ayaso","year":"2008","journal-title":"PhD thesis, Massachusetts Institute of Technology"},{"issue":"6","key":"2026032901020943500_ref004","doi-asserted-by":"crossref","first-page":"1261","DOI":"10.1137\/S0097539700379383","article-title":"Fast, distributed approximation algorithms for positive linear programming with applications to flow control","volume":"33","author":"Bartal","year":"2004","journal-title":"SIAM Journal on Computing"},{"key":"2026032901020943500_ref005","volume-title":"Parallel and Distributed Computation: Numerical Methods","author":"Bertsekas","year":"1989"},{"key":"2026032901020943500_ref006","doi-asserted-by":"crossref","DOI":"10.1109\/CDC.2005.1582620","volume-title":"Convergence in multiagent coordination, consensus, and flocking","author":"Blondel","year":"2005"},{"key":"2026032901020943500_ref007","doi-asserted-by":"crossref","DOI":"10.1137\/S0036144503423264","article-title":"Fastest mixing Markov chain on a graph","author":"Boyd","year":"2004","journal-title":"SIAM Review"},{"issue":"SI","key":"2026032901020943500_ref008","first-page":"2508","article-title":"Randomized gossip algorithms","volume":"14","author":"Boyd","year":"2006","journal-title":"IEEE\/ACM Transaction on Networking"},{"key":"2026032901020943500_ref009","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex Optimization","author":"Boyd","year":"2004"},{"key":"2026032901020943500_ref010","volume-title":"Throughput guarantees through maximal scheduling in wireless networks","author":"Chaporkar","year":"2005"},{"key":"2026032901020943500_ref011","article-title":"Optimal cross-layer congestion control, routing and scheduling design in ad-hoc wireless networks","author":"Chen","year":"2006","journal-title":"in IEEE INFOCOM"},{"key":"2026032901020943500_ref012","doi-asserted-by":"crossref","DOI":"10.1109\/ICDE.2004.1320018","article-title":"Approximate aggregation techniques for sensor databases","author":"Considine","year":"2004"},{"key":"2026032901020943500_ref013","first-page":"556","article-title":"The throughput of switches with and without speedup","author":"Dai","year":"2000"},{"key":"2026032901020943500_ref014","article-title":"Algebraic gossip: A network coding approach to optimal multiple rumor mongering","volume":"14","author":"Deb","year":"2006","journal-title":"IEEE\/ACM Transactions on Networking"},{"key":"2026032901020943500_ref015","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-5320-4","volume-title":"Large Deviations Techniques and Applications","author":"Dembo","year":"1998","edition":"Second"},{"key":"2026032901020943500_ref016","doi-asserted-by":"crossref","first-page":"726","DOI":"10.1214\/aoap\/1019487508","article-title":"Analysis of a non-reversible Markov chain sampler","volume":"10","author":"Diaconis","year":"2000","journal-title":"Annals of Applied Probability"},{"issue":"1","key":"2026032901020943500_ref017","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01898359","article-title":"Moderate growth and random walk on finite groups","volume":"4","author":"Diaconis","year":"1994","journal-title":"Geometric and Functional Analysis"},{"key":"2026032901020943500_ref018","doi-asserted-by":"crossref","DOI":"10.1145\/1127777.1127791","article-title":"Geographic gossip: Efficient aggregation for sensor networks","author":"Dimakis","year":"2006"},{"issue":"6","key":"2026032901020943500_ref019","doi-asserted-by":"crossref","first-page":"2568","DOI":"10.1109\/TIT.2006.874379","article-title":"Optimal throughputdelay scaling in wireless networks-part I: The fluid model","volume":"52","author":"El Gamal","year":"2006","journal-title":"IEEE Transactions on Information Theory"},{"issue":"130","key":"2026032901020943500_ref020","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/0024-3795(90)90206-R","article-title":"On the convergence of asynchronous paracontractions with applications to tomographic reconstruction from incomplete data","author":"Elsner","year":"1990","journal-title":"Linear Algebra and Its Applications"},{"key":"2026032901020943500_ref021","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-27820-7_8","article-title":"Scale free aggregation in sensor networks","author":"Enachescu","year":"2004"},{"key":"2026032901020943500_ref022","article-title":"Distributed cross-layer algorithms for the optimal control of multi-hop wireless networks","author":"Eryilmaz","year":"2009","journal-title":"IEEE\/ACM Transactions on Networking (accepted to appear)"},{"issue":"2","key":"2026032901020943500_ref023","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1016\/0022-0000(85)90041-8","article-title":"Probabilistic counting algorithms for data base applications","volume":"31","author":"Flajolet","year":"1985","journal-title":"Journal of Computer and System Science"},{"issue":"l","key":"2026032901020943500_ref024","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1109\/TCOM.1977.1093711","article-title":"A minimum delay routing algorithm using distributed computation","volume":"COM-25","author":"Gallager","year":"1977","journal-title":"IEEE Transactions on Communications"},{"key":"2026032901020943500_ref025","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey"},{"key":"2026032901020943500_ref026","first-page":"303","article-title":"On-line end-to-end congestion control","author":"Garg","year":"2002"},{"issue":"4","key":"2026032901020943500_ref027","doi-asserted-by":"crossref","first-page":"546","DOI":"10.1109\/JSAC.2003.810496","article-title":"Randomized scheduling algorithms for high-aggregate bandwidth switches","volume":"21","author":"Giaccone","year":"2003","journal-title":"IEEE Journal of Select Areas Communication High-performance Electronic Switches\/Routers for High-speed Internet"},{"issue":"2","key":"2026032901020943500_ref028","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1109\/18.825799","article-title":"The capacity of wireless networks","volume":"46","author":"Gupta","year":"2000","journal-title":"IEEE Transaction on Information Theory"},{"key":"2026032901020943500_ref029","article-title":"Link scheduling in polynomial time","volume":"34","author":"Sasaki","year":"1988","journal-title":"IEEE Transactions on Information Theory"},{"key":"2026032901020943500_ref030","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511810817","volume-title":"Matrix Analysis","author":"Horn","year":"1985"},{"key":"2026032901020943500_ref031"},{"issue":"6","key":"2026032901020943500_ref032","doi-asserted-by":"crossref","first-page":"988","DOI":"10.1109\/TAC.2003.812781","article-title":"Coordination of groups of mobile autonomous agents using nearest neighbor rules","volume":"48","author":"Jadbabaie","year":"2003","journal-title":"IEEE Transactions on Automatic Control"},{"key":"2026032901020943500_ref033","doi-asserted-by":"crossref","DOI":"10.1109\/ISIT.2007.4557418","article-title":"Low delay scheduling in wireless network","author":"Jung","year":"2007"},{"key":"2026032901020943500_ref034","article-title":"Minimizing rate of convergence for iterative algorithms","author":"Jung","year":"2009","journal-title":"IEEE Transactions on Information Theory (accepted to appear)"},{"key":"2026032901020943500_ref035","doi-asserted-by":"crossref","article-title":"Quantized consensus","author":"Kashyap","DOI":"10.1109\/ISIT.2006.261862"},{"issue":"3","key":"2026032901020943500_ref036","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1057\/palgrave.jors.2600523","article-title":"Rate control for communication networks: Shadow prices, proportional fairness and stability","volume":"49","author":"Kelly","year":"1998","journal-title":"Journal of the Operational Research Society"},{"key":"2026032901020943500_ref037","first-page":"482","article-title":"Gossip-based computation of aggregate information","author":"Kempe","year":"2003"},{"key":"2026032901020943500_ref038","volume-title":"A decentralized algorithm for spectral analaysis","author":"Kempe","year":"2004"},{"issue":"3","key":"2026032901020943500_ref039","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1145\/945721.945736","article-title":"Selective information dissemination in P2P networks: Problems and solutions","volume":"32","author":"Koubarakis","year":"2003","journal-title":"SIGMOD Record"},{"key":"2026032901020943500_ref040","article-title":"A tutorial on cross-layer optimization in wireless networks","author":"Lin","year":"2006","journal-title":"Submitted, Available Through csl.uiuc.edu\/rsrikant"},{"key":"2026032901020943500_ref041","article-title":"Impact of imperfect scheduling in wireless networks","author":"Lin","year":"2005","journal-title":"in IEEE INFOCOM"},{"key":"2026032901020943500_ref042","unstructured":"N.\n              Linial\n             and A.Wigderson, \u201cLecture notes on Expander Graphs,\u201d http:\/\/www.math.ias.edu\/\u223cavi\/BOOKS\/expanderbookr1.pdf."},{"key":"2026032901020943500_ref043","first-page":"85","volume-title":"Microsurveys in Discrete Probability, DIMACS Series in Discrete Mathematics and Theoretical Computer Science","author":"Lovasz","year":"1998"},{"key":"2026032901020943500_ref044","first-page":"448","article-title":"A parallel approximation algorithm for positive linear programming","author":"Luby","year":"1993"},{"issue":"4","key":"2026032901020943500_ref045","doi-asserted-by":"crossref","first-page":"1460","DOI":"10.1109\/TIT.2008.917663","article-title":"Product multi-commodity flow in wireless networks","volume":"54","author":"Madan","year":"2008","journal-title":"IEEE Transactions on Information Theory"},{"issue":"SI","key":"2026032901020943500_ref046","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1145\/844128.844142","article-title":"Tag: A tiny aggregation service for ad-hoc sensor networks","volume":"36","author":"Madden","year":"2002","journal-title":"SIGOPS Operating Systems Review"},{"key":"2026032901020943500_ref047","doi-asserted-by":"crossref","DOI":"10.1145\/1071690.1064215","article-title":"Coupon replication systems","author":"Massouli\u00b4e","year":"2005","journal-title":"ACM SIGMETRICS\/Performance"},{"issue":"2","key":"2026032901020943500_ref048","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1109\/90.769767","article-title":"iSLIP: A scheduling algorithm for input-queued switches","volume":"7","author":"McKeown","year":"1999","journal-title":"IEEE Transactions on Networking"},{"key":"2026032901020943500_ref049","first-page":"296","article-title":"Achieving 100% throughput in an input-queued switch","author":"McKeown","year":"1996"},{"key":"2026032901020943500_ref050","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4471-3267-7","volume-title":"Markov Chains and Stochastic Stability","author":"Meyn","year":"1993"},{"key":"2026032901020943500_ref051","doi-asserted-by":"crossref","DOI":"10.1145\/1140103.1140283","article-title":"Maximizing throughput in wireless network via gossiping","author":"Modiano","year":"2006","journal-title":"ACM SIGMETRICS\/Performance"},{"issue":"3","key":"2026032901020943500_ref052","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1561\/0400000003","article-title":"Mathematical aspects of mixing times in Markov chains","volume":"1","author":"Tetali","year":"2006","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"2026032901020943500_ref053","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-75142-7_41","article-title":"Fully distributed algorithms for convex optimization problems","author":"Mosk-Aoyama","year":"2007"},{"key":"2026032901020943500_ref054","article-title":"Information dissemination via network coding","author":"Mosk-Aoyama","year":"2006","journal-title":"in IEEE ISIT"},{"issue":"7","key":"2026032901020943500_ref055","doi-asserted-by":"crossref","first-page":"2997","DOI":"10.1109\/TIT.2008.924648","article-title":"Fast distributed algorithms for computing separable functions","volume":"54","author":"Mosk-Aoyama","year":"2008","journal-title":"IEEE Transactions on Information Theory"},{"key":"2026032901020943500_ref056","article-title":"Distributed subgradient methods for multi-agent optimization","author":"Nedic","year":"2008"},{"key":"2026032901020943500_ref057","doi-asserted-by":"crossref","DOI":"10.1145\/167088.167127","article-title":"Linear programming without the matrix","author":"Papadimitriou","year":"1993"},{"key":"2026032901020943500_ref058","volume-title":"Oxford Studies in Probability","author":"Penrose","year":"2003"},{"key":"2026032901020943500_ref059","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1145\/1030194.1015508","article-title":"Modeling and performance analysis of bittorrent-like peer-to-peer networks","author":"Qiu","year":"2004","journal-title":"ACM SIGCOMM"},{"key":"2026032901020943500_ref060","doi-asserted-by":"crossref","DOI":"10.1145\/2492101.1555365","article-title":"Network adiabatic theorem: An efficient randomized protocol for contention resolution","author":"Rajagopalan","year":"2009","journal-title":"ACM SIGMETRICS\/Performance"},{"key":"2026032901020943500_ref061","doi-asserted-by":"crossref","DOI":"10.2307\/3062153","article-title":"Entropy waves, The zig-zag graph product, and new constant-degree expanders and extractors","author":"Reingold","year":"2002","journal-title":"Annals of Mathematics"},{"key":"2026032901020943500_ref062","volume-title":"Network Flows and Monotropic Optimization","author":"Rockafellar","year":"1984"},{"key":"2026032901020943500_ref063","first-page":"4530","article-title":"On traveling salesperson problems for Dubins\u2019 vehicle: stochastic and dynamic environments","author":"Savla","year":"2005"},{"key":"2026032901020943500_ref064","article-title":"Stable algorithms for input queued switches","author":"Shah","year":"2001"},{"key":"2026032901020943500_ref065","article-title":"Optimal scheduling algorithm for input queued switch","author":"Wischik","year":"2006","journal-title":"IEEE INFOCOM"},{"key":"2026032901020943500_ref066","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-8176-8216-3","volume-title":"The Mathematics of Internet Congestion Control","author":"Srikant","year":"2004"},{"key":"2026032901020943500_ref067","doi-asserted-by":"crossref","first-page":"1936","DOI":"10.1109\/9.182479","article-title":"Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks","volume":"37","author":"Tassiulas","year":"1992","journal-title":"IEEE Transactions on Automatic Control"},{"key":"2026032901020943500_ref068","doi-asserted-by":"crossref","DOI":"10.1145\/380752.380839","article-title":"Non-approximability results for optimization problems on bounded degree instances","author":"Trevisan","year":"2001","journal-title":"ACM STOC"},{"key":"2026032901020943500_ref069","volume-title":"PhD dissertation, Lab. Information and Decision Systems","author":"Tsitsiklis","year":"1984"},{"key":"2026032901020943500_ref070"}],"container-title":["Foundations and Trends\u00ae in Networking"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.emerald.com\/ftnet\/article-pdf\/3\/1\/1\/10963304\/1300000014en.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/www.emerald.com\/ftnet\/article-pdf\/3\/1\/1\/10963304\/1300000014en.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T18:13:46Z","timestamp":1777486426000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.emerald.com\/ftnet\/article\/3\/1\/1\/1323413\/Gossip-Algorithms"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,6,2]]},"references-count":70,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,6,2]]}},"URL":"https:\/\/doi.org\/10.1561\/1300000014","relation":{},"ISSN":["1554-057X","1554-0588"],"issn-type":[{"value":"1554-057X","type":"print"},{"value":"1554-0588","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,6,2]]}}}