Reduction of the total execution time to achieve the optimal k-node reliability of distributed computing systems using a novel heuristic algorithm

A distributed computing system is a collection of processor-memory pairs co nnected by communication links. A k-node set is a subset of total nodes in a distributed computing system. A k-node set with capacity constraint is a k-node set that possesses sufficient node capacity. Because computing the r eliability of a distributed computing system is generally an NP-hard proble m, an adequate k-node set with a given capacity constraint must be determin ed by an effective algorithm with an approximate reliability. Relatively fe w investigations, namely an exact method and a k-tree reduction method, hav e examined k-node reliability optimization with capacity constraint. Such i nvestigations either spent an exponential time or rarely obtained an optima l solution. Therefore, in this work, we present a novel heuristic algorithm to reduce the computational time and deviation from an exact solution. The proposed algorithm has simple independent steps, including selection of k- node sets according to a node's weight or a link's weight. The number of se lected k-node sets is either one or two, thereby spending less time to comp ute the reliability of k-node sets. Computational results demonstrate that the proposed algorithm is more effective and provides a better solution for a large distributed computing system than those in previous investigations . (C) 2000 Elsevier Science B.V. All rights reserved.