Quasirandom Rumor Spreading

Computer Science – Data Structures and Algorithms

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

33 pages, parts of the results appeared in SODA'08 and ICALP'09

Scientific paper

We propose and analyse a quasirandom analogue of the classical push model for disseminating information in networks ("randomized rumor spreading"). In the classical model, in each round each informed vertex chooses a neighbor at random and informs it, if it was not before. It is known that this simple protocol succeeds in spreading a rumor from one vertex to all others within O(log n) rounds on complete graphs, hypercubes, random regular graphs, Erdos-Renyi random graph and Ramanujan graphs with high probability. In the quasirandom model, we assume that each vertex has a (cyclic) list of its neighbors. Once informed, it starts at a random position of the list, but from then on informs its neighbors in the order of the list. Surprisingly, irrespective of the orders of the lists, the above mentioned bounds still hold. In some cases even better bounds than for the classical model can be shown.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Quasirandom Rumor Spreading does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Quasirandom Rumor Spreading, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quasirandom Rumor Spreading will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-642763

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.