 max planck institut
informatik # MPI-INF or MPI-SWS or Local Campus Event Calendar

 << Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
Title: On Quasirandom Rumor Spreading Anna Huber Max-Planck-Institut für Informatik - D1 AG1 Mittagsseminar (own work) D1We use this to send out email in the morning. AG Audience English
Date: Friday, 19 September 2008 13:30 30 Minutes Saarbrücken E1 4 024
 Randomized rumor spreading is a protocol for disseminating information in a network. The problem is as follows. Initially, one vertex of a finite, undirected connected graph has some piece of information (rumor''). Each round, each vertex knowing the rumor tells it to a neighbor chosen uniformly at random (resulting in that this vertex now also knows the rumor and starts gossipping in the next round). The question is how many rounds are necessary to inform all vertices of the graph with high probability. Results of Frieze and Grimmett show that in a complete graph on $n$ vertices, this simple protocol succeeds in spreading the rumor from one node to all others within $(1 + o(1))(\log_2(n) + \ln(n))$ rounds. Benjamin Doerr, Tobias Friedrich and Thomas Sauerwald proposed a quasirandom analogue of the randomized rumor spreading 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 gossipping 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 then shown that, independent of the choice of the cyclic permutations, this protocol also needs $O(\log n)$ rounds only to inform all other nodes. We show that for complete graphs we do not even lose a constant factor, that is, independent of the cyclic permutations, the protocol informs all nodes in $(1 + o(1)) (\log_2(n) + \ln(n))$ rounds. Joint work with Benjamin Doerr.
Name(s): Anna Huber