BROADCASTING WITH A BOUNDED FRACTION OF FAULTY NODES

We consider the problem of broadcasting a message from one processor ( called the source) to n other processors, We adopt the 1-port half-dup lex model in which every processor (node) can communicate with at most one other node in a unit of time and during this period one of the co mmunicating nodes can only send information and the other can only rec eive it. The source is fault-free but all other nodes are subject to p ermanent failures. A faulty node can receive the message but cannot re lay it. The fraction of faulty nodes is bounded by a constant. We cons ider nonadaptive broadcasting algorithms working correctly in the pres ence of faulty nodes and investigate their worst-case running time, We also show lower bounds for broadcasting time under this scenario. Our main result is the construction of a fault-tolerant broadcasting algo rithm whose running time is less than 1.73 times larger than optimal, for sufficiently large n. (C) 1997 Academic Press.