Broadcasting with Many Faulty Links.
Rastislav Kráľovič, Richard Královič, Peter Růžička · 2003
We study the problem of broadcasting in point-to-point networks with faulty links. The usual approach in which the number of faulty links in each step is bounded by a fixed constant does not reflect the intuition that the probability of a certain link to fail while transmitting a particular message is a fixed constant. In our model the number of faulty links in a given step depends on the total number of links used in that step. We are interested in fault-resilience of networks for broadcast in this model: in which class of networks the broadcasting time is proportional to their diameter. We show that toroidal grids of constant dimension are fault-resilient in our model, but on the other hand complete d-ary trees and cliques are not.