A fault-tolerant broadcast scheme in the star graph under the single-port, half-duplex communication model
Satoshi Fujita · IEEE Transactions on Computers · 1999
In this paper, we propose a simple and nonadaptive fault-tolerant broadcast scheme in the star graph under the single-port, half-duplex communication model. The proposed scheme can tolerate up to n-2 vertex and/or edge faults in the star graph with nl vertices and takes at most n+4 more time units than an optimal nonadaptive broadcast scheme. Since it takes at least [log/sub 2/(nl)]=/spl Theta/(n log n) time units to complete a broadcast under the single port model, the gap between lower and upper bounds is fairly small.