Found an issue? Give us feedback

Hyper Article en Lig...arrow_drop_down

Hyper Article en Ligne

Other ORP type

Data sources: Hyper Article en Ligne

Select content type to embed

All Research products

arrow_drop_down

<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>

COPY SCRIPT

For further information contact us at helpdesk@openaire.eu

Low Randomness Rumor Spreading via Hashing

Name: Low Randomness Rumor Spreading via Hashing
Keywords: Parallel and Distributed Computing, Rumor Spreading, [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Randomness

appsOther research productkeyboard_double_arrow_right Other ORP type English Funded by:NSERC

Authors: Giakkoupis, George; Sauerwald, Thomas; Sun, He; Woelfel, Philipp;

Low Randomness Rumor Spreading via Hashing

- Summary
- Subjects
- References
  (24)

Abstract

We consider the classical rumor spreading problem, where a piece of information must be disseminated from a single node to all n nodes of a given network. We devise two simple push-based protocols, in which nodes choose the neighbor they send the information to in each round using pairwise independent hash functions, or a pseudo-random generator, respectively. For several well-studied topologies our algorithms use exponentially fewer random bits than previous protocols. For example, in complete graphs, expanders, and random graphs only a polylogarithmic number of random bits are needed in total to spread the rumor in O(log n) rounds with high probability. Previous explicit algorithms require Omega(n) random bits to achieve the same round complexity. For complete graphs, the amount of randomness used by our hashing-based algorithm is within an O(log n)-factor of the theoretical minimum determined by [Giakkoupis and Woelfel, 2011].

Keywords

Parallel and Distributed Computing, Rumor Spreading, [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Randomness

24 references, page 1 of 3

IEEE Transactions on Information Theory and IEEE/ACM Transactions on Networking, 52(6):2508-2530, 2006.

F. Chierichetti, S. Lattanzi, and A. Panconesi. Almost tight bounds on rumour spreading with conductance. In 42nd ACM Symposium on Theory of Computing (STOC'10), pages 399-408, 2010. [OpenAIRE]

A. Coja-Oghlan. On the Laplacian eigenvalues of Gn,p. Combinatorics, Probability & Computing, 16(6):923-946, 2007.

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

Electronic Notes in Discrete Mathematics, 34:335-339, 2009.

B. Doerr, T. Friedrich, and T. Sauerwald. Quasirandom rumor spreading. In 19th ACMSIAM Symposium on Discrete Algorithms (SODA'08), pages 773-781, 2008.

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

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

Theoretical Computer Science, 410(36):3414-3427, 2009.

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

chevron_left
1
2
3
chevron_right

Found an issue? Give us feedback

Funded by

NSERC

Related to Research communities

Neuroinformatics