ANALYSIS AND DESIGN OF A FAULT-TOLERANT TREE ARCHITECTURE

Tree structures have been widely used in the design of distributed systems. One distinct advantage of the tree architecture is the O(logN) speed of information exchange between any two nodes of an N-node system. Further, the tree architecture can naturally map several important classes of problems that can be described as divide-and-conquer algorithms. In this paper we present the analysis and design of a new fault-tolerant tree structure; the L-tree. The L-tree is formed by augmenting the simplex binary tree with redundant links only. The performance and fault-tolerance of the L-tree are evaluated and compared with previously proposed augmented tree architectures. The results of comparison show that the proposed architecture is more reliable than the existing fault-tolerant tree structures. The L-tree also permits simple algorithmic routine. We present a distributed routing algorithm that finds near-optimal routes even under node failures. © 1990 Taylor and Francis Ltd.