Rumor Spreading on Random Regular Graphs and Expanders

Details Rumor Spreading on Random Regular Graphs and Expanders Rumor Spreading on Random Regular Graphs and Expanders

2010-02-18

arxiv.org/abs/1002.3518v1

Mathematics

Combinatorics

18 pages

Scientific paper

Broadcasting algorithms are important building blocks of distributed systems. In this work we investigate the typical performance of the classical and well-studied push model. Assume that initially one node in a given network holds some piece of information. In each round, every one of the informed nodes chooses independently a neighbor uniformly at random and transmits the message to it. In this paper we consider random networks where each vertex has degree d, which is at least 3, i.e., the underlying graph is drawn uniformly at random from the set of all d-regular graphs with n vertices. We show that with probability 1 - o(1) the push model broadcasts the message to all nodes within (1 + o(1))C_d ln n rounds, where C_d = 1/ ln(2(1-1/d)) - 1/(d ln(1 - 1/d)). In particular, we can characterize precisely the effect of the node degree to the typical broadcast time of the push model. Moreover, we consider pseudo-random regular networks, where we assume that the degree of each node is very large. There we show that the broadcast time is (1+o(1))C ln n with probability 1 - o(1), where C= 1/ ln 2 + 1, is the limit of C_d as d grows.

Affiliated with

Also associated with

No associations

Rating

Rumor Spreading on Random Regular Graphs and Expanders 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 Rumor Spreading on Random Regular Graphs and Expanders, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rumor Spreading on Random Regular Graphs and Expanders will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-405869