Optimal broadcasting in faulty trees

We consider broadcasting a message from one node of a tree to all other nod es. In the presence of up to ii 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 ii faults, is the k-vulnerability of B. This is the maximum slowdown incurred by B due to the lack of a priori k nowledge of fault location, for at most k faults. This measure of fault tol erance is similar to the competitive factor of on-line algorithms: in both cases, the performance of an algorithm lacking some crucial information is compared to the performance of an "off-line" algorithm, one that is given t his information as input. It is also the first known tool to measure and co mpare fault tolerance of broadcasting schemes in trees. We seek broadcastin g schemes with low vulnerability, working for tree networks. It turns out t hat schemes that give the best broadcasting time in a fault-free environmen t may have very high vulnerability, i.e., poor fault tolerance, for some tr ees. The main result of this paper is an algorithm that, given an arbitrary tree T and an integer k, computes a broadcasting scheme B with lowest poss ible k-vulnerability among all schemes working for T. Our algorithm has run ning time O(kn(2) + n(2) log n), where n is the size of the tree. We also g ive an algorithm to find a "universally fault-tolerant" broadcasting scheme in a tree T: one that approximates the lowest possible k-vulnerability, fo r all k simultaneously. (C) 2000 Academic Press.