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