Probabilistic Analysis of Rumor-Spreading Time

References

• Acan H, Collevecchio A, Mehrabian A, Nick W (2015) On the push&pull protocol for rumour spreading. Proc. 2015 ACM Sympos. Principles Distributed Comput., Donostia-San Sebastián, Spain, 405–412.Crossref, Google Scholar
• Angluin D, Aspnes J, Eisenstat D (2008) Fast computation by population protocols with a leader. Distributed Comput. 21(2):183–199.Crossref, Google Scholar
• Berger N, Borgs C, Chayes JT, Saberi A (2005) On the spread of viruses on the internet. Proc. 16th Annual ACM-SIAM Sympos. Discrete Algorithms, Vancouver, 301–310.Google Scholar
• Censor-Hillel K, Haeupler B, Kelner J, Maymounkov P (2012) Global computation in a poorly connected world: Fast rumor spreading with no dependence on conductance. Proc. 44th Annual ACM Sympos. Theory Comput (STOC) (ACM, New York), 961–970.Crossref, Google Scholar
• Chierichetti F, Lattanzi S, Panconesi A (2011) Rumor spreading in social networks. Theoret. Comput. Sci. 412(24):2602–2610.Crossref, Google Scholar
• Clementi A, Crescenzi P, Doerr C, Fraigniaud P, Pasquale F, Silvestri R (2015) Rumor spreading in random evolving graphs. Random Structures Algorithms 48(2):290–312.Crossref, Google Scholar
• Comets F, Delarue F, Schott R (2014) Information transmission under random emission constraints. Environ. Model. Software 23(6):973–1009.Google Scholar
• Comets F, Gallesco C, Popov S, Vachkovskaia M (2016) Constrained information transmission on Erdös-Rényi graphs. Markov Processes Related Fields 22:111–138.Google Scholar
• Daley D, Kendall DG (1965) Stochastic rumours. IMA J. Appl. Math. 1(1):42–55.Crossref, Google Scholar
• Daum S, Kuhn F, Maus Y (2016) Rumor spreading with bounded indegree. Structural Information and Communication Complexity, Lecture Notes in Computer Science, vol. 9988 (Springer, Cham, Switzerland), 323–339.Crossref, Google Scholar
• Demers A, Gealy M, Greene D, Hauser C, Irish W, Larson J, Shenker S, Sturgis H, Swinehart D, Terry D (1987) Epidemic algorithms for replicated database maintenance. Proc. 6th Annual ACM Sympos. Principles Distributed Comput. (ACM, New York), 1–12.Crossref, Google Scholar
• Feige U, Peleg D, Raghavan P, Upfal E (1990) Randomized broadcast in networks. Random Structures Algorithms 1(4):447–460.Crossref, Google Scholar
• Fountoulakis N, Panagiotou K (2013) Rumor spreading on random regular graphs and expanders. Random Structures Algorithms 43(2):201–220.Crossref, Google Scholar
• Frieze A, Grimmet G (1985) The shortest-path problem for graphs with random arc-lengths. Discrete Appl. Math. 10(1):57–77.Crossref, Google Scholar
• Ganesh AJ (2015) Rumour spreading on graphs. Technical report, University of Bristol, Bristol, UK.Google Scholar
• Giakkoupis G (2011) Tight bounds for rumor spreading in graphs of a given conductance. Proc. 28th Intern. Sympos. Theoret. Aspects Comput. Sci., LIPIcs, vol. 9 (Dagstuhl, Wadern, Germany), 57–68.Google Scholar
• Giakkoupis G (2014) Tight bounds for rumor spreading with vertex expansion. Proc. 25th Annual ACM-SIAM Sympos. Discrete Algorithms, Portland, Oregon, 801–815.Crossref, Google Scholar
• Harchol-Balter M, Leighton T, Lewin D (1999) Resource discovery in distributed networks. Proc. 18th Annual ACM Sympos. Principles Distributed Computing (ACM, New York), 229–237.Crossref, Google Scholar
• Janson S (2014) Tail bounds for sums of geometric and exponential variables. Technical report, Uppsala University, Uppsala, Sweden.Google Scholar
• Karp R, Schindelhauer C, Shenker S, Vocking B (2000) Randomized rumor spreading. Proc. 41st Annual Sympos. Foundations Comput. Sci., (IEEE, Piscataway, NJ), 565–574.Crossref, Google Scholar
• Kempe D, Dobra A, Gehrke J (2003) Gossip-based computation of aggregate information. Proc. 44th Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 482–491.Crossref, Google Scholar
• Lebensztayn E, Machado AF, Rodríguez PM (2011) On the behaviour of a rumour process with random stifling. Environ. Model. Software 26(4):517–522.Crossref, Google Scholar
• Mocquard Y, Robert S, Sericola B, Anceaume E (2016) Analysis of the propagation time of a rumour in large-scale distributed systems. Proc. 15th IEEE Internat. Sympos. Network Comput. Appl. (IEEE, Piscataway, NJ), 216–223.Crossref, Google Scholar
• Molchanov S, Whitmeyer JM (2010) Two Markov models of the spread of rumors. J. Math. Sociol. 34(3):157–166.Crossref, Google Scholar
• Panagiotou K, Speidel L (2017) Asynchronous rumor spreading on random graphs. Algorithmica 78(3):968–989.Crossref, Google Scholar
• Panagiotou K, Perez-Gimenez X, Sauerwald T, Sun H (2015) Randomized rumor spreading: The effect of the network topology. Combinatorics Probab. Comput. 24(2):457–479.Crossref, Google Scholar
• Pittel B (1987) On spreading a rumor. SIAM J. Appl. Math. 47(1):213–223.Crossref, Google Scholar
• Pittel B (1990) On a Daley-Kendall model of random rumours. J. Appl. Probab. 27(1):14–27.Crossref, Google Scholar
• Sericola B (2013) Markov Chains. Theory, Algorithms and Applications, Applied Stochastic Methods Series (John Wiley & Sons, Hoboken, NJ).Crossref, Google Scholar