关键词: 集群计算系统, k-to-l-out-of-n模型, 二元决策图

Abstract: To analyze the performance of cluster computing systems with identical computing power but different failure distribution, a k-to-l-out-of-n structure was used to model system performance, and a new analytical method based on Binary Decision Diagram (BDD) was proposed for the performance analysis. A new and efficient BDD algorithm that makes full use of the special k-to-l-out-of-n structure was also proposed using a top-down manner, which solved the problem that the traditional bottom-up generation algorithm must generate a large number of intermediate redundant nodes. Then the proposed BDD was used to efficiently calculate the probability of the system being at a specific performance level. At last, some examples were provided to illustrate the proposed BDD-based performance analysis methodology as well as its efficiency in analyzing large-scale cluster computing systems.

Key words: cluster computing system, k-to-l-out-of-n model, Binary Decision Diagram (BDD)