Feasibility and complexity of broadcasting with random transmission failures
Andrzej Pelc, David Peleg · 2005
We consider fault-tolerant broadcasting in the message passing and radio models under a probabilistic failure model. At each step, the transmitter of each node may fail independently with fixed probability p 1. For the radio model we show that almost-safe broadcasting in time O (opt + log n) (where opt is the optimal fault-free broadcasting time) is impossible for some graphs, even with omission failures, and we give an almost-safe broadcasting algorithm of time O(opt • log n) for any graph, for both types of failures.