Quasirandom Rumor Spreading: An Experimental Analysis

Details Quasirandom Rumor Spreading: An Experimental Analysis Quasirandom Rumor Spreading: An Experimental Analysis

2010-12-24

arxiv.org/abs/1012.5357v1

Computer Science

Data Structures and Algorithms

14 pages, appeared in ALENEX'09

Scientific paper

We empirically analyze two versions of the well-known "randomized rumor spreading" protocol to disseminate a piece of information in networks. In the classical model, in each round each informed node informs a random neighbor. In the recently proposed quasirandom variant, each node 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. While for sparse random graphs a better performance of the quasirandom model could be proven, all other results show that, independent of the structure of the lists, the same asymptotic performance guarantees hold as for the classical model. In this work, we compare the two models experimentally. This not only shows that the quasirandom model generally is faster, but also that the runtime is more concentrated around the mean. This is surprising given that much fewer random bits are used in the quasirandom process. These advantages are also observed in a lossy communication model, where each transmission does not reach its target with a certain probability, and in an asynchronous model, where nodes send at random times drawn from an exponential distribution. We also show that typically the particular structure of the lists has little influence on the efficiency.

Affiliated with

Also associated with

No associations

Rating

Quasirandom Rumor Spreading: An Experimental Analysis 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: An Experimental Analysis, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quasirandom Rumor Spreading: An Experimental Analysis will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-642789