A Heuristic Algorithm for Reliability Modeling and Analysis of Grid Systems

Author

Dai, Yuan-Shun ; Xie, Min ; Wang, Xiaolong

Author_Institution

Dept. of Comput. & Inf. Sci., Indiana Univ.-Purdue Univ., Indianapolis, IN

Volume

37

Issue

2

fYear

2007

fDate

3/1/2007 12:00:00 AM

Firstpage

189

Lastpage

200

Abstract

Grid computing focuses on large-scale resource sharing. Using a general reliability model for grid computing to relax some impractical assumptions, a heuristic algorithm is presented to evaluate grid program/service reliability. The heuristic algorithm is based on two heuristic criteria that determine the significance of an entity and prune those insignificant ones. Through algorithm analysis, the heuristic algorithm is shown to have a linear complexity. This is much better than the previous algorithms, which are of exponential complexity. Another advantage of the heuristic algorithm is that the running time is controllable by adjusting the parameter of significant level (SL) and significant rate. A regression method is proposed to adjust the SL and predict the running time. Two examples are given

Keywords

Bayes methods; computational complexity; grid computing; reliability theory; Bayesian analysis; distributed computing; exponential complexity; grid computing; grid systems analysis; heuristic algorithm; large-scale resource sharing; regression method; reliability modeling; service reliability; significant level; Algorithm design and analysis; Application software; Collaborative software; Distributed computing; Graph theory; Grid computing; Heuristic algorithms; Large-scale systems; Reliability theory; Resource management; Bayesian analysis; distributed computing; graph theory; grid program/service reliability; heuristic algorithm;

fLanguage

English

Journal_Title

Systems, Man and Cybernetics, Part A: Systems and Humans, IEEE Transactions on

Publisher

ieee

ISSN

1083-4427

Type

jour

DOI

10.1109/TSMCA.2006.889479

Filename

4100774