AN EFFECTIVE ALGORITHM FOR OPTIMAL K-TERMINAL RELIABILITY OF DISTRIBUTED SYSTEMS

Abstract

Distributed system provides a cost-effective means of enhancing a computer system’s performance in areas such as throughput, fault-tolerance, and reliability optimization. Consequently, the reliability optimization of a distributed system has become a critical issue. A K-terminal reliability is defined as the probability that a specified set, K, of nodes is connected in a distributed system. A K-terminal reliability optimization with an order (the number of nodes in K-terminal) constraint problem is to select a K-terminal of nodes in a distributed system such that the K-terminal reliability is maximal and possesses sufficient order. It is evident that this is an NP-hard problem. This paper presents a heuristic method to reduce the computational time and the absolute error from the exact solution. The proposed algorithm is based on not only a simple method to compute each node’s weight and each link’s weight, but also an effective objective function to evaluate the weight of node sets. Before appending one node to a current selected set, instead of computing the weight of all links and all nodes of each set, only the weight of a node, which is adjacent to the current selected set, and links between the node and the current selected set are accumulated. Then the proposed algorithm depends on the maximum weight to find an adequate node and assign it to the current selected set in a sequential manner until the order of K-terminal constraint is satisfied. Reliability computation is performed only once, thereby saving much time and the absolute error of the proposed algorithm from exact solution is very small.