Abstract
We consider the problem of broadcasting a message from one processor (called the source) tonother 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 largen.
Original language | English (US) |
---|---|
Pages (from-to) | 11-20 |
Number of pages | 10 |
Journal | Journal of Parallel and Distributed Computing |
Volume | 42 |
Issue number | 1 |
DOIs | |
State | Published - Apr 10 1997 |
Externally published | Yes |
ASJC Scopus subject areas
- Software
- Theoretical Computer Science
- Hardware and Architecture
- Computer Networks and Communications
- Artificial Intelligence