Reliability Quantification of the Tree Structure Based Distributed System

Due to unpredictable failures in the network or the components, tree-structure, one of the common structures of distributed system, is partial fault-tolerance. A simple but effective method to enhance the reliability of a tree is to maintain a neighbor set for each node in the tree. Obviously, a larger neighbor set results in a higher reliability, but also increases the maintenance cost. The contribution of the paper is to give an algorithm to figure out the reliability of a tree theoretically. We also give an analysis of the results that obtained through the algorithm with various inputs.