Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, March 19, 2009, 12:15 pm
Duration: This information is not available in the database
Location: CAB G51
Speaker: Anna Huber (Max-Planck-Institut für Informatik, Saarbrücken)
Randomized rumor spreading is a protocol for disseminating information in a network. Initially, one vertex of a finite, undirected connected graph has some piece of information (''rumor''). In each round, every vertex that knows the rumor tells it to a neighbor chosen uniformly at random. Results of Frieze and Grimmett show that in a complete graph on n vertices, this protocol spreads the rumor from one node to all others within (1 + o(1))(log2(n) + ln(n)) rounds with probability 1-o(1). This was improved to log2(n) + ln(n) + h(n) for every h \in ω(1) by Pittel.
Doerr, Friedrich and Sauerwald proposed a quasirandom analogue of this model. Here, each vertex has a cyclic permutation of its neighbors. When first passing the rumor, it chooses a neighbor uniformly at random. All subsequent gossiping is done to the successors of this vertex in the cyclic permutation. For complete graphs, hypercubes and a broader range of random graphs it was shown that this protocol also needs O(log n) rounds only to inform all other nodes.
We give a precise analysis of the evolution in the case of a complete graph on n vertices and show that this protocol also informs all nodes in (1 + o(1))(log2(n) + ln(n))rounds with probability 1-o(1).
Joint work with Benjamin Doerr and Nikolaos Fountoulakis.
Automatic MiSe System Software Version 1.4803M | admin login