Optimal adaptive broadcasting with a bounded fraction of faulty nodes

We consider broadcasting among n processors, f of which can be faulty. A fa ult-free processor, called the source, holds a piece of information which h as to be transmitted to all other fault-free processors. We assume that the fraction f/n of faulty processors is bounded by a constant gamma < 1. Tran smissions are fault free. Faults are assumed to be of the crash type: fault y processors do not send or receive messages. We use the whispering model: pairs of processors communicating in one round must farm a matching. A faul t-free processor sending a message to another processor becomes aware of wh ether this processor is faulty or fault free and can adapt future transmiss ions accordingly. The main result of the paper is a broadcasting algorithm working in O(log n) rounds and using O(n) messages of logarithmic size, in the worst case. This is an improvement of the result from [17] where O((log n)(2)) rounds were used. Our method also gives the first algorithm for ada ptive distributed fault diagnosis in O(log n) rounds.