Rapid almost-complete broadcasting in faulty networks

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 c(G)−1, where c(G) is the edge connectivity of the communication graph, or a fraction α 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(Dlogn) 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 α<0.55) the remaining constant number of vertices can be informed in the same time, i.e. O(logn).