Download now Free registration required
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, of sent messages can be lost depending on which quantity is larger. As the main result the authors 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 (Dlog n) where D is the diameter of the network and n is the number of vertices.
- Format: PDF
- Size: 220.24 KB