About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
FOCS 1984
Conference paper
The multi-tree approach to reliability in distributed networks
Abstract
Consider a network of asynchronous processors communicating by sending messages over unreliable lines. There are many advantages to restricting all communications to a spanning tree. To overcome the possible failure of k '<k edges, we describe a communication protocol which uses k rooted spanning trees having the property that for every vertex v the paths from v to the root are edge-disjoint. An algorithm to find two such trees in a 2 edge-connected graph is described that runs in time proportional to the number of edges in the graph. This algorithm has a distributed version which finds the two trees even when a single edge fails during their construction. The two trees them may be used to transform certain centralized algorithms to distributed, reliable and efficient ones.