کاهش زمان اجرای کل برای دستیابی به قابلیت اطمینان بهینه K-گره از سیستم های محاسبات توزیع شده با استفاده از یک الگوریتم اکتشافی جدید

A distributed computing system is a collection of processor–memory pairs connected 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 reliability of a distributed computing system is generally an NP-hard problem, an adequate k-node set with a given capacity constraint must be determined by an effective algorithm with an approximate reliability. Relatively few investigations, namely an exact method and a k-tree reduction method, have examined k-node reliability optimization with capacity constraint. Such investigations either spent an exponential time or rarely obtained an optimal 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 selected k-node sets is either one or two, thereby spending less time to compute 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.

Recent developments in computer networking and low cost computational elements have led to increasing interest in distributed computing systems (DCS). DCS, a collection of processor–memory pairs connected by communication links, is logically integrated by a distributed communication network. The communication subnet may be a geographically dispersed collection of communication processors or a local area network [1], [2] and [3]. The numerous merits of using DCS include improved resource sharing, enhanced fault tolerance and high reliability. The economic benefits of resource sharing largely account for the importance of DCS. A DCS focuses on providing efficient communication among various nodes, thereby increasing their reliability and making their service available to more users [4]. Designing such systems must consider system reliability which heavily relies on the topological layout of communication links [5], [6] and [7]. The topology of a network can be characterized by a linear graph. These network topologies can be characterized by their network reliability, message-delay, or network capacity. The performance characteristics depend on many properties of the network topology [8], [9], [10], [11], [12] and [13]: the number of ports at each node (degree of a node) and the number of links. The number of links directly impacts the system reliability. Previous literature provides reliability optimization models of DCS that optimize source to destination reliability, k-out-of-n systems reliability and overall system reliability [7], [14] and [15]. Two reliability optimization models have been presented in [16]. As defined, k-node reliability is the probability that nodes in the k-node set (subset of the set of processing elements) in the DCS are connected. The exact method (EM) [17] and the k-tree reduction method [18] have examined k-node reliability optimization with capacity constraint. These either spent an exponential time or barely obtained an optimal solution. This work focuses mainly on how to compute nearly maximum system reliability objectives with capacity constraint. The fact that computing the reliability of DCS is a NP-hard problem explains why an adequate solution must be derived in a very short time. More specifically, deriving a solution with an exact solution as possible is of primary concern. Therefore, this work computes the reliability of a subset of the set of processing elements such that the reliability is maximized and the specified capacity constraint is satisfied.

This work presents a novel heuristic algorithm to derive a k-node set with capacity constraint of maximal reliability. The proposed algorithm is compared with the EM and the k-tree reduction method for various topologies. According to that comparison, the proposed algorithm is more efficient in execution time for a large DCS than those methods. The proposed algorithm based on taking a short time to evaluate the weight of each node and the weight of each link. According to the weights of nodes and links, the algorithm can accurately predict which node will be included to obtain a better k-node set. The proposed algorithm can also effectively reduce the number of reliability computations. Because the number of reliability computations is either one or two, the proposed algorithm can provide the desired performance. Further, when the proposed algorithm fails to provide an exact solution, the deviation from the exact solution is only slight.