Universally fault-tolerant broadcasting in trees

We consider broadcasting a message from one node of a tree to all other nodes. In the presence of up to k link failures the tree becomes disconnected, and only nodes in the connected component C containing the source can be informed. The maximum ratio between the time used by a broadcasting scheme B to inform C and the optimal time to inform C, taken over all components C yielded by configurations of at most k faults, is the k-vulnerability of B. This is the maximum slowdown incurred by B due to the lack of a priori knowledge of fault location, for at most k faults. Since the upper bound k on the number of faults is not always known, it is important to design broadcasting schemes that behave well under any possible number of faults. It turns out that achieving the lowest possible k-vulnerability for all k simultaneously is impossible for some trees. Hence a natural goal is to seek, for any tree T, a broadcasting scheme that simultaneously approximates the lowest possible k-vulnerability for every k, up to a given constant factor c (independent of L). We describe a polynomial algorithm which decides if such a “universally fault-tolerant” broadcasting scheme exists for given T and c, and constructs such a scheme if it exists