TY  - THES
T1  - Randomized rumor spreading in social networks and complete graphs
A1  - Fouz,Mahmoud
Y1  - 2012/07/23
N2  - This thesis deals with two rumor spreading problems. In the first part, we study the rumor spreading problem in social networks modelled by preferential attachment graphs. We consider the push-pull strategy by Karp, Schindelhauer, Shenker, and Vöcking [FOCS 2000], where in each round, each vertex chooses a random neighbor and exchanges information with it. We prove the following. The push-pull strategy delivers a message to all nodes within \Theta(\log n) rounds with high probability, where n is the number of nodes in the graph. The best known bound so far was O(\log^2 n) by Chierichetti, Lattanzi, and Panconesi [TCS 2011]. If we slightly modify the protocol so that contacts are chosen uniformly from all neighbors but the one contacted in the previous round, then this time reduces to \Theta(\logn/\log\log n). This is asymptotically optimal since it matches the diameter of the graph. In an asynchronous version of the protocol, the running time is shown to be even O(\sqrt{\log n}). In the second part, we consider the rumor spreading problem on the complete graph. We propose a new push protocol that achieves an asymptotically optimal time of (1+o(1))\log^2 n. It needs only O(n f(n)) calls, where f(n) = \omega(1) can be arbitrary. The protocol is robust against random node failures. We also extend it to deal with adversarial node failures efficiently.
KW  - Randomisierung
KW  - Algorithmus
KW  - Laufzeit
KW  - Vollständiger Graph
CY  - Saarbrücken
PB  - Universitäts- und Landesbibliothek
AD  - Postfach 151141, 66041 Saarbrücken
UR  - http://scidok.sulb.uni-saarland.de/volltexte/2012/4903
ER  -