Mathematics – Combinatorics
Scientific paper
2009-04-30
Mathematics
Combinatorics
15 pages
Scientific paper
Broadcasting algorithms are of fundamental importance for distributed systems engineering. In this paper we revisit the classical and well-studied push protocol for message broadcasting. Assuming that initially only one node has some piece of information, at each stage every one of the informed nodes chooses randomly and independently one of its neighbors and passes the message to it. The performance of the push protocol on a fully connected network, where each node is joined by a link to every other node, is very well understood. In particular, Frieze and Grimmett proved that with probability 1-o(1) the push protocol completes the broadcasting of the message within (1 +/- \epsilon) (log_2 n + ln n) stages, where n is the number of nodes of the network. However, there are no tight bounds for the broadcast time on networks that are significantly sparser than the complete graph. In this work we consider random networks on n nodes, where every edge is present with probability p, independently of every other edge. We show that if p > f(n)ln n/ n, where f(n) is any function that tends to infinity as n grows, then the push protocol broadcasts the message within (1 +/- \epsilon) (log_2 n + ln n) stages with probability 1-o(1). In other words, in almost every network of density d such that d > f(n)ln n, the push protocol broadcasts a message as fast as in a fully connected network. This is quite surprising in the sense that the time needed remains essentially unaffected by the fact that most of the links are missing.
Fountoulakis Nikolaos
Huber Anna
Panagiotou Konstantinos
No associations
LandOfFree
The Speed of Broadcasting in Random Networks: Density Does Not Matter 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 The Speed of Broadcasting in Random Networks: Density Does Not Matter, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Speed of Broadcasting in Random Networks: Density Does Not Matter will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-443691