A recursively heuristic method for the reliability optimization of a distributed computing system

摘要

The reliability optimization of a distributed computing system is generally an NP-hard problem. The reliability of a k-node set with capacity constraint is defined as the probability that a subset of the set of processing elements in system is connected and possesses sufficient node capacity. Relative investigations, namely an exact method and a k-tree reduction method, have examined an optimal or nearly optimal k-node set with capacity constraint. Such investigations can not effectively reduce either the computational time complexity or the deviation from an exact solution. The paper presents a recursively heuristic method to overcome these difficulties. The proposed algorithm selects reasonable k-node sets by starting at two nodes which are incident with a link of maximal reliability and a node which has either maximal capacity or maximal degree, respectively. When the starting node is taken, the recursive sub-procedure is run. The sub-procedure adds an adjacent node which connected by a link of maximal reliability to selected set and calls itself again and again until an adequate k-node set is found. By doing so, the sub-procedure finds all of the adequate k-node sets and returns an optimal k-node set to the algorithm. In addition, the sub-procedure omits the reliability computation when an adequate set that has occurred before is selected. For the reason that the reliability of a subset of a set is at least as large as the reliability of the set, the reduction processing is used for decreasing the order of the set. The number of selected sets is very small, therefore the proposed algorithm can reduce execution time and complexity. Moreover, the deviation from the exact solution is improved. Compared with existing algorithms on various distributed computing system topologies, our results demonstrate that the proposed algorithm is more efficient in execution time than conventional methods.