Broadcasting with a Bounded Fraction of Faulty Nodes

✍ Scribed by Leszek Gąsieniec; Andrzej Pelc

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 312 KB
• Volume: 42
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.1997.1303

✦ Synopsis

We consider the problem of broadcasting a message from one processor (called the source) to n other processors. We adopt the 1-port half-duplex 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 communicating nodes can only send information and the other can only receive it. The source is fault-free but all other nodes are subject to permanent failures. A faulty node can receive the message but cannot relay it. The fraction of faulty nodes is bounded by a constant. We consider nonadaptive broadcasting algorithms working correctly in the presence 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 algorithm whose running time is less than 1.73 times larger than optimal, for sufficiently large n.