计算具有不可靠结点分布式网络可靠度的一个因子分解算法  

A Factoring Algorithm for Reliability Evaluating of Distributed Networks with Imperfect Nodes

作　　者：孙艳蕊[1] 崔立彦[1] 张祥德[1] 

机构地区：[1]东北大学理学院,沈阳110004

出　　处：《计算机科学》2002年第4期111-113,71,共4页Computer Science

基　　金：国家自然科学基金(编号:19701006)

摘　　要：1引言 随着计算机技术的迅速发展,计算机已在各个领域得到广泛的应用.越来越多的部门,象通讯、金融、国防、工业控制等领域,对计算机产生了很强的依赖性.这些系统的计算机一旦发生故障,将带来不可估量的损失.分布式网络以其可靠、坚固、快速响应、易于修改和扩充、资源共享等优点,而被广泛应用,其可靠度的计算成为人们关注的重要课题.目前,国内外学者对一般网络可靠度进行了较多的研究[1～4,8,9],但对于具有不可靠结点的分布式网络的分布程序可靠度(Distribut-ed Program Reliability,DPR)的研究还不多见[6,7].This paper presents several reliability preserving reductions. By using these reductions and factoring theorem, an efficient algorithm was proposed to evaluate the distributed program reliability(DPR)of distributed networks with imperfect nodes. The time complexity of the algorithm is O(N·( |V|+ |E|)). where N is the total number of the nodes in the generated tree, |V|and|E|are the node and link number of the network, respectively. In order to show the efficiency of the algorithm, the DPRs of different networks were evaluated by computer experiments on Pentium 120 PC. The number of leaves in generated tree and overall computing time are much less than that of other algorith-m.

关 键 词：分布式网络 可靠度 因子分解算法 计算机网络 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]