A fault-tolerant broadcast scheme in the star graph under the single-port, half-duplex communication model

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 n! vertices and takes at most n + 4 more time units than an optimal nonadaptive broadcast scheme. Since it takes at least [log(2)(n!)] = theta(nlog n) time units to complete a broadcast under the single port model. the gap between lower and upper bounds is fairly small.