Feasibility and complexity of broadcasting with random transmission failures

Fault-tolerant broadcasting in the message passing and radio models is considered under a probabilistic failure model. At each step, the transmitter of each node may fail with fixed constant probability p<1, and failures are independent. Both node-omission and malicious transmission failures are studied. Our goal is to establish conditions on feasibility and to estimate the (synchronous) time complexity of almost-safe broadcasting (i.e., broadcasting which is correct with probability at least 1−1/n for n-node graphs and for sufficiently large n) under these scenarios. If only node-omission failures are assumed, almost-safe broadcasting is feasible for any p<1, in both communication models. For malicious transmission failures, almost-safe broadcasting in the message passing model is feasible iff p<1/2, and in the radio model it is feasible iff p<(1−p)Δ+1, where Δ is the maximum degree of the network. For the time complexity of almost-safe broadcasting, a number of upper and lower bounds are given in the various models.