nach oben

Distributed Computing

Erschienen in:

15.09.2017

Breaking the \(\log n\) barrier on rumor spreading

verfasst von: Chen Avin, Robert Elsässer

Erschienen in: Distributed Computing | Ausgabe 6/2018

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

\(O(\log n)\) 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)\) is also known for this special case. Under the assumption of this model and with a natural addition that nodes can call a partner once they learn its address (e.g., its IP address) we present a new distributed, address-oblivious and robust algorithm that uses push&pull with pointer jumping to spread a rumor to all nodes in only \(O(\sqrt{\log n})\) rounds, w.h.p. This algorithm can also cope with \(F= O(n/2^{\sqrt{\log n}})\) node failures, in which case all but O(F) nodes become informed within \(O(\sqrt{\log n})\) rounds, w.h.p.

Vorheriger Artikel Communication-efficient randomized consensus

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

In this paper with high probably or w.h.p. is with probability at least \(1-n^{-1-\varOmega (1)}\).

A call, in which no data is sent (e.g., the rumor, or a pointer), is not considered as a message.

Note that in [23] the authors consider arbitrary node weights, which are 1 / n for all nodes in our case.

Avin, C., Elsässer, R.: Faster rumor spreading: breaking the logn barrier. In: Proceedings of the 27th International Symposium on Distributed Computing–DISC 2013, pp. 209–223. Springer, Berlin (2013)

Avin, C., Lotker, Z., Pignolet, Y.-A., Turkel, I.: From caesar to twitter: structural properties of elites and rich-clubs. CoRR abs/1111.3374 (2012)

Berenbrink, P., Elsässer, R., Friedetzky, T.: 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 , pp. 155–164 (2008)

Berenbrink, P., Elsässer, R., Sauerwald, T.: Communication complexity of quasirandom rumor spreading. Algorithmica 72(2), 467–492 (2015)MathSciNetCrossRefMATH

Censor-Hillel, K., Haeupler, B., Kelner, J., Maymounkov, P.: 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, pp. 961–970 (2012)

Chaintreau, A., Fraigniaud, P., Lebhar, E.: Opportunistic spatial gossip over mobile social networks. In: Proceedings of the 1st Workshop on Online Social Networks , pp. 73–78 (2008)

Chung, F., Lu, L.: Connected components in random graphs with a given degree expected sequence. Ann. Comb. 6, 125–145 (2002)MathSciNetCrossRefMATH

Deb, S., Médard, M., Choute, C.: Algebraic gossip: a network coding approach to optimal multiple rumor mongering. IEEE Trans. Inf. Theory 52(6), 2486–2507 (2006)CrossRefMATH

Demers, A., Greene, D., Hauser, C., Irish, W., Larson, J., Shenker, S., Sturgis, H., Swinehart, D., Terry, D.: Epidemic algorithms for replicated database maintenance. In: Proceedings of the 6th Annual ACM Symposium on Principles of Distributed Computing , pp. 1–12 (1987)

10.

Doerr, B., Fouz, M., Friedrich, T.: Social networks spread rumors in sublogarithmic time. In: Proceeding of the 43rd Annual ACM Symposium on Theory of Computing , pp. 21–30 (2011)

11.

Doerr, B., Friedrich, T., Sauerwald, T.: Quasirandom rumor spreading. In: Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 773–781 (2008)

12.

Doerr, B., Friedrich, T., Sauerwald, T.: Quasirandom rumor spreading: expanders, Push vs. Pull and Robustness. In: Proceedings of the 36th International Colloquium on Automata, Languages and Programming, pp. 366–377 (2009)

13.

Elsässer, R., Sauerwald, T.: On the runtime and robustness of randomized broadcasting. In: Proceedings of the 17th International Symposium on Algorithms and Computation, pp. 349–358 (2006)

14.

Elsässer, R., Sauerwald, T.: The power of memory in randomized broadcasting. In: Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 218–227 (2008)

15.

Feige, U., Peleg, D., Raghavan, P., Upfal, E.: Randomized broadcast in networks. Random Struct. Algorithms 1(4), 447–460 (1990)MathSciNetCrossRefMATH

16.

Fountoulakis, N., Panagiotou, K., Sauerwald, T.: Ultra-fast rumor spreading in social networks. In: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1642–1660 (2012)

17.

Frieze, A.M., Grimmett, G.R.: The shortest-path problem for graphs with random arc-lengths. Discrete Appl. Math. 10(1), 57–77 (1985)MathSciNetCrossRefMATH

18.

Giakkoupis, G.: Tight bounds for rumor spreading in graphs of a given conductance. In: 28th International Symposium on Theoretical Aspects of Computer Science, pp. 57–68 (2011)

19.

Gurevich, M., Keidar, I.: Correctness of gossip-based membership under message loss. SIAM J. Comput. 39(8), 3830–3859 (2010)MathSciNetCrossRefMATH

20.

Haeupler, B.: Simple, fast and deterministic gossip and rumor spreading. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 705–716 (2013)

21.

Haeupler, B., Malkhi, D.: Optimal gossip with direct addressing. In: Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, New York, NY, PODC ’14, pp. 176–185. ACM (2014)

22.

Harchol-Balter, M., Leighton, T., Lewin, D.: Resource discovery in distributed networks. In: Proceedings of the 18th Annual ACM symposium on Principles of Distributed Computing, pp. 229–237 (1999)

23.

Karp, R., Schindelhauer, C., Shenker, S., Vöcking, B.: Randomized rumor spreading. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, pp. 565–574 (2000)

24.

Kempe, D., Dobra, A., Gehrke, J.: Gossip-based computation of aggregate information. In: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, pp. 482–491 (2003)

25.

Kempe, D., Kleinberg, J., Tardos, É.: Maximizing the spread of influence through a social network. In: Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 137–146 (2003)

26.

Kutten, S., Peleg, D.: Asynchronous resource discovery in peer-to-peer networks. Comput. Netw. 51(1), 190–206 (2007)CrossRefMATH

27.

Kutten, S., Peleg, D., Vishkin, U.: Deterministic resource discovery in distributed networks. Theory Comput. Syst. 36(5), 479–495 (2003)MathSciNetCrossRefMATH

28.

Leighton, F.T.: Introduction to Parallel Algorithms and Architectures. Morgan Kaufmann, San Francisco (1992)MATH

29.

Lotker, Z., Patt-Shamir, B., Pavlov, E., Peleg, D.: Minimum-weight spanning tree construction in o (log log n) communication rounds. SIAM J. Comput. 35(1), 120–131 (2005)MathSciNetCrossRefMATH

30.

Mahlmann, P., Schindelhauer, C.: Distributed random digraph transformations for peer-to-peer networks. In: Proceedings of the 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures, pp. 308–317 (2006)

31.

Melamed, R., Keidar, I.: Araneola: a scalable reliable multicast system for dynamic environments. In: Proceedings Third IEEE International Symposium on Network Computing and Applications, 2004 (NCA 2004), pp. 5–14. IEEE (2004)

32.

Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, New York (2005)CrossRefMATH

33.

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

34.

Raab, M., Steger, A.: “Balls into bins”—a simple and tight analysis. In: Proceedings of the RANDOM/APPROX. pp. 159–170 (1998)

35.

Sauerwald, T.: On mixing and edge expansion properties in randomized broadcasting. Algorithmica 56(1), 51–88 (2010)MathSciNetCrossRefMATH

Titel: Breaking the barrier on rumor spreading
verfasst von: Chen Avin
Robert Elsässer
Publikationsdatum: 15.09.2017
Verlag: Springer Berlin Heidelberg
Erschienen in: Distributed Computing / Ausgabe 6/2018
Print ISSN: 0178-2770
Elektronische ISSN: 1432-0452
DOI: https://doi.org/10.1007/s00446-017-0312-4

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 6/2018

Communication-efficient randomized consensus

Time-communication impossibility results for distributed transactional memory

How many cooks spoil the soup?

A resource-competitive jamming defense

Simple multi-party set reconciliation