BROADCASTING WITH LINEARLY BOUNDED TRANSMISSION FAULTS

We consider broadcasting with a linearly bounded number of transmissio n failures. For a constant parameter 0 < alpha < 1 we assume that at m ost alpha i faulty transmissions can occur during the first i time uni ts of the communication process, for every natural number i. Every inf ormed node can transmit information to at most one neighbor in a unit of time. Faulty transmissions have no effect. We investigate worst-cas e optimal non-adaptive broadcasting lime under this fault model, for s everal communication networks. We show, e.g., that for the n-node line network this time is linear in n, if alpha < 1/2, and exponential oth erwise. For the hypercube and the complete graph, broadcasting in the linearly bounded fault model can be performed in time logarithmic in t he number of nodes. (C) 1998 Elsevier Science B.V. All rights reserved .