Rapid Almost-Complete Broadcasting in Faulty Networks

Details Rapid Almost-Complete Broadcasting in Faulty Networks Rapid Almost-Complete Broadcasting in Faulty Networks

2007-03-23

arxiv.org/abs/cs/0703122v1

Computer Science

Distributed, Parallel, and Cluster Computing

Conference: Sirocco 2007

Scientific paper

This paper studies the problem of broadcasting in synchronous point-to-point networks, where one initiator owns a piece of information that has to be transmitted to all other vertices as fast as possible. The model of fractional dynamic faults with threshold is considered: in every step either a fixed number $T$, or a fraction $\alpha$, of sent messages can be lost depending on which quantity is larger. As the main result we show that in complete graphs and hypercubes it is possible to inform all but a constant number of vertices, exhibiting only a logarithmic slowdown, i.e. in time $O(D\log n)$ where $D$ is the diameter of the network and $n$ is the number of vertices. Moreover, for complete graphs under some additional conditions (sense of direction, or $\alpha<0.55$) the remaining constant number of vertices can be informed in the same time, i.e. $O(\log n)$.

Affiliated with

Also associated with

No associations

Rating

Rapid Almost-Complete Broadcasting in Faulty Networks 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 Rapid Almost-Complete Broadcasting in Faulty Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rapid Almost-Complete Broadcasting in Faulty Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-360877