research-article

Rumor Spreading and Conductance

Authors:

Flavio Chierichetti,

George Giakkoupis,

Silvio Lattanzi,

Alessandro PanconesiAuthors Info & Claims

Journal of the ACM (JACM), Volume 65, Issue 4

Article No.: 17, Pages 1 - 21

https://doi.org/10.1145/3173043

Published: 12 April 2018 Publication History

Abstract

In this article, we study the completion time of the PUSH-PULL variant of rumor spreading, also known as randomized broadcast. We show that if a network has n nodes and conductance ϕ then, with high probability, PUSH-PULL will deliver the message to all nodes in the graph within O(log n/ϕ) many communication rounds. This bound is best possible. We also give an alternative proof that the completion time of PUSH-PULL is bounded by a polynomial in log n/ϕ, based on graph sparsification. Although the resulting asymptotic bound is not optimal, this proof shows an interesting and, at the outset, unexpected connection between rumor spreading and graph sparsification. Finally, we show that if the degrees of the two endpoints of each edge in the network differ by at most a constant factor, then both PUSH and PULL alone attain the optimal completion time of O(log n/ϕ), with high probability.

References

[1]

Yossi Azar, Andrei Z. Broder, Anna R. Karlin, and Eli Upfal. 1999. Balanced allocations. SIAM J. Comput. 29, 1 (1999), 180--200.

Digital Library

[2]

Joshua Batson, Daniel A. Spielman, Nikhil Srivastava, and Shang-Hua Teng. 2013. Spectral sparsification of graphs: Theory and algorithms. Commun. ACM 56, 8 (2013), 87--94.

Digital Library

[3]

P. Berenbrink, R. Elsässer, and T. Friedetzky. 2008. Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems. In Proceedings of the 27th ACM Symposium on Principles of Distributed Computing (PODC’08). 155--164.

Digital Library

[4]

S. P. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. 2006. Gossip algorithms: Design, analysis and applications. IEEE Trans. Inf. Theory 52, 6 (2006), 1653--1664.

[5]

Keren Censor-Hillel, Bernhard Haeupler, Jonathan A. Kelner, and Petar Maymounkov. 2012. Global computation in a poorly connected world: Fast rumor spreading with no dependence on conductance. In Proceedings of the 44th ACM Symposium on Theory of Computing (STOC’12). 961--970.

Digital Library

[6]

Keren Censor-Hillel and Hadas Shachnai. 2011. Fast information spreading in graphs with large weak conductance. In Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA’11). 440--448.

Digital Library

[7]

J. Cheeger. 1970. A lower bound for the smallest eigenvalue of the laplacian. Problems in Analysis. 195--199.

[8]

F. Chierichetti, S. Lattanzi, and A. Panconesi. 2009. Rumor spreading in social networks. In Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP’09). 375--386.

Digital Library

[9]

Flavio Chierichetti, Silvio Lattanzi, and Alessandro Panconesi. 2010. Almost tight bounds for rumour spreading with conductance. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC’10). 399--408.

Digital Library

[10]

Flavio Chierichetti, Silvio Lattanzi, and Alessandro Panconesi. 2010. Rumour spreading and graph conductance. In Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA’10). 1657--1663.

Digital Library

[11]

F. R. K. Chung. 1997. Spectral Graph Theory. American Mathematical Society.

[12]

A. J. Demers, D. H. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. E. Sturgis, D. C. Swinehart, and D. B. Terry. 1987. Epidemic algorithms for replicated database maintenance. In Proceedings of the 6th ACM Symposium on Principles of Distributed Computing (PODC’87).

Digital Library

[13]

B. Doerr, M. Fouz, and T. Friedrich. 2011. Social networks spread rumors in sublogarithmic time. In Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC’11). 21--30.

Digital Library

[14]

B. Doerr, T. Friedrich, and T. Sauerwald. 2008. Quasirandom rumor spreading. In Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms (SODA’08). 1964--1991.

Digital Library

[15]

B. Doerr, T. Friedrich, and T. Sauerwald. 2009. Quasirandom rumor spreading: Expanders, push vs. pull, and robustness. In Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP’09). 366--377.

Digital Library

[16]

D. Dubhashi and A. Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press.

Digital Library

[17]

R. Elsässer. 2006. On the communication complexity of randomized broadcasting in random-like graphs. In Proceedings of the 18th ACM Symposium on Parallel Algorithms and Architectures (SPAA’06). 148--157.

Digital Library

[18]

Uriel Feige, David Peleg, Prabhakar Raghavan, and Eli Upfal. 1990. Randomized broadcast in networks. Random Struct. Algori. 1, 4 (1990), 447--460.

[19]

Nikolaos Fountoulakis, Konstantinos Panagiotou, and Thomas Sauerwald. 2012. Ultra-fast rumor spreading in social networks. In Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA’12). 1642--1660.

Digital Library

[20]

A. Frieze and G. Grimmett. 1985. The shortest-path problem for graphs with random arc-lengths. Discr. Appl. Math. 1, 10 (1985), 57--77.

[21]

George Giakkoupis. 2011. Tight bounds for rumor spreading in graphs of a given conductance. In Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS’11). 57--68.

[22]

George Giakkoupis. 2014. Tight bounds for rumor spreading with vertex expansion. In Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms (SODA’14). 801--815.

Digital Library

[23]

George Giakkoupis and Thomas Sauerwald. 2012. Rumor spreading and vertex expansion. In Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA’12). 1623--1641.

Digital Library

[24]

George Giakkoupis, Thomas Sauerwald, and Alexandre Stauffer. 2014. Randomized rumor spreading in dynamic graphs. In Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP’14). 495--507.

[25]

George Giakkoupis, Thomas Sauerwald, He Sun, and Philipp Woelfel. 2012. Low randomness rumor spreading via hashing. In Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS’12). 314--425.

[26]

Bernhard Haeupler. 2013. Simple, fast and deterministic gossip and rumor spreading. In Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms (SODA’13). 705--716.

Digital Library

[27]

Mark Jerrum and Alistair Sinclair. 1989. Approximating the permanent. SIAM J. Comput. 18, 6 (1989), 1149--1178.

Digital Library

[28]

R. Karp, C. Schindelhauer, S. Shenker, and B. Vöcking. 2000. Randomized rumor spreading. In Proceedings of the 41st IEEE Symposium on Foundations of Computer Science (FOCS’00). 565--574.

Digital Library

[29]

J. Leskovec, K. J. Lang, A. Dasgupta, and M. W. Mahoney. 2008. Statistical properties of community structure in large social and information networks. In Proceedings of the 17th International Conference on World Wide Web (WWW’08). 695--704.

Digital Library

[30]

Milena Mihail, Christos H. Papadimitriou, and Amin Saberi. 2006. On certain connectivity properties of the Internet topology. J. Comput. Syst. Sci. 72, 2 (2006), 239--251.

Digital Library

[31]

Michael Mitzenmacher and Eli Upfal. 2005. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis. Cambridge University Press.

Digital Library

[32]

D. Mosk-Aoyama and D. Shah. 2008. Fast distributed algorithms for computing separable functions. IEEE Trans. Inf. Theory 54, 7 (2008), 2997--3007.

Digital Library

[33]

B. Pittel. 1987. On spreading a rumor. SIAM J. Appl. Math. 47, 1 (1987), 213--223.

Digital Library

[34]

Thomas Sauerwald. 2010. On mixing and edge expansion properties in randomized broadcasting. Algorithmica 56, 1 (2010), 51--88.

Digital Library

[35]

Thomas Sauerwald and Alexandre Stauffer. 2011. Rumor spreading and vertex expansion on regular graphs. In Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA’11). 462--475.

Digital Library

[36]

D. A. Spielman and S. H. Teng. 2004. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the 36th ACM Symposium on Theory of Computing (STOC’04). 81--90.

Digital Library

[37]

Daniel A. Spielman and Shang Hua Teng. 2011. Spectral sparsification of graphs. SIAM J. Comput. 40, 4 (2011), 981--1025.

Digital Library

Cited By

Korman AVacus R(2024)Early adapting to trends: self-stabilizing information spread using passive communicationDistributed Computing10.1007/s00446-024-00462-837:4(335-362)Online publication date: 22-Feb-2024
https://doi.org/10.1007/s00446-024-00462-8
Hahn-Klimroth MKaaser D(2023)On Reconstructing the Patient Zero from Sensor Measurements2023 IEEE 43rd International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS57875.2023.00065(1-11)Online publication date: Jul-2023
https://doi.org/10.1109/ICDCS57875.2023.00065
Panagiotou KReisser S(2023)Asymptotics for pull on the complete graphStochastic Processes and their Applications10.1016/j.spa.2023.01.017159(541-563)Online publication date: May-2023
https://doi.org/10.1016/j.spa.2023.01.017
Show More Cited By

Index Terms

Rumor Spreading and Conductance
1. Mathematics of computing
  1. Probability and statistics
    1. Probabilistic algorithms
2. Theory of computation
  1. Design and analysis of algorithms
    1. Distributed algorithms
    2. Graph algorithms analysis

Recommendations

Almost tight bounds for rumour spreading with conductance
STOC '10: Proceedings of the forty-second ACM symposium on Theory of computing

We show that if a connected graph with $n$ nodes has conductance φ then rumour spreading, also known as randomized broadcast, successfully broadcasts a message within ~O(φ^-1 • log n), many rounds with high probability, regardless of the source, by using ...
Breaking the $$\log n$$logn barrier on rumor spreading

$$O(\log n)$$O(logn) rounds has been a well known upper bound for rumor spreading using push&pull in the random phone call model (i.e., uniform gossip in the complete graph). A matching lower bound of $$\varOmega (\log n)$$Ω(logn) is also known for this ...
On the bit communication complexity of randomized rumor spreading
SPAA '10: Proceedings of the twenty-second annual ACM symposium on Parallelism in algorithms and architectures

We study the communication complexity of rumor spreading in the random phone-call model. Suppose nplayers communicate in parallel rounds, where in each round every player calls a randomly selected communication partner. A player u is allowed to exchange ...

Comments

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 65, Issue 4

Distributed Computing, Cryptography, Distributed Computing, Cryptography, Coding Theory, Automata Theory, Complexity Theory, Programming Languages, Algorithms, Invited Paper Foreword and Databases

August 2018

307 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/3208081

Editor:
Éva Tardos
Cornell University

Issue’s Table of Contents

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 April 2018

Accepted: 01 December 2017

Revised: 01 November 2017

Received: 01 January 2014

Published in JACM Volume 65, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

ERC Starting Grant DMAP
ANR Project NDFusion
ANR Project PAMELA
Google Focused Research Award
SIR
BiCi (Bertinoro international Center for informatics)

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
723
Total Downloads

Downloads (Last 12 months)42
Downloads (Last 6 weeks)7

Reflects downloads up to 24 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Korman AVacus R(2024)Early adapting to trends: self-stabilizing information spread using passive communicationDistributed Computing10.1007/s00446-024-00462-837:4(335-362)Online publication date: 22-Feb-2024
https://doi.org/10.1007/s00446-024-00462-8
Hahn-Klimroth MKaaser D(2023)On Reconstructing the Patient Zero from Sensor Measurements2023 IEEE 43rd International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS57875.2023.00065(1-11)Online publication date: Jul-2023
https://doi.org/10.1109/ICDCS57875.2023.00065
Panagiotou KReisser S(2023)Asymptotics for pull on the complete graphStochastic Processes and their Applications10.1016/j.spa.2023.01.017159(541-563)Online publication date: May-2023
https://doi.org/10.1016/j.spa.2023.01.017
Nugroho SWeinmann ASchindelhauer C(2023)Adding Pull to Push Sum for Approximate Data AggregationStabilization, Safety, and Security of Distributed Systems10.1007/978-3-031-44274-2_7(75-89)Online publication date: 2-Oct-2023
https://dl.acm.org/doi/10.1007/978-3-031-44274-2_7
Korman AVacus RMilani AWoelfel P(2022)Early Adapting to Trends: Self-Stabilizing Information Spread using Passive CommunicationProceedings of the 2022 ACM Symposium on Principles of Distributed Computing10.1145/3519270.3538415(235-245)Online publication date: 20-Jul-2022
https://dl.acm.org/doi/10.1145/3519270.3538415
Zhu LHe L(2022)Pattern dynamics analysis and parameter identification of time delay-driven rumor propagation model based on complex networksNonlinear Dynamics10.1007/s11071-022-07717-8110:2(1935-1957)Online publication date: 27-Jul-2022
https://doi.org/10.1007/s11071-022-07717-8
Guleva VAndreeva PVaganov D(2021)Subgraphs of Interest Social Networks for Diffusion Dynamics PredictionEntropy10.3390/e2304049223:4(492)Online publication date: 20-Apr-2021
https://doi.org/10.3390/e23040492
Granese FGorla DPalamidessi C(2021)Enhanced models for privacy and utility in continuous-time diffusion networksInternational Journal of Information Security10.1007/s10207-020-00530-720:5(763-782)Online publication date: 1-Oct-2021
https://dl.acm.org/doi/10.1007/s10207-020-00530-7
Pourmiri AMans BEmek YCachin C(2020)Tight Analysis of Asynchronous Rumor Spreading in Dynamic NetworksProceedings of the 39th Symposium on Principles of Distributed Computing10.1145/3382734.3405720(263-272)Online publication date: 31-Jul-2020
https://dl.acm.org/doi/10.1145/3382734.3405720
Daknama RPanagiotou KReisser S(2020)Robustness of randomized rumour spreadingCombinatorics, Probability and Computing10.1017/S0963548320000310(1-42)Online publication date: 12-Aug-2020
https://doi.org/10.1017/S0963548320000310
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents