A NEW HEURISTIC APPROACH FOR RELIABILITY OPTIMIZATION OF DISTRIBUTED COMPUTING SYSTEMS SUBJECT TO CAPACITY CONSTRAINTS

Distributed Computing Systems (DCS) have become a major trend in compu ter system design today, because of their high speed and reliable perf ormance. Reliability is an important performance parameter in DCS desi gn. In the reliability analysis of a DCS, the term of K-Node Reliabili ty (KNR) is defined as the probability that all nodes in K (a subset o f all processing elements) are connected. In this paper, we propose a simple, easily programmed heuristic method for obtaining the optimal d esign of a DCS in terms of maximizing reliability subject to a capacit y constraint. The first part of this paper presents a heuristic algori thm which selects an optimal set of K-nodes that maximizes the KNR in a DCS subject to the capacity constraint. The second part of the paper describes a new approach that uses a K-tree disjoint reduction method to speed up the KNR evaluation. Compared with existing algorithms on various DCS topologies, the proposed algorithm finds a suboptimal desi gn much more efficiently in terms of both execution time and space tha n an exact and exhaustive method for a large DCS.