摘要
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.
出处
《计算机科学》
CSCD
北大核心
2002年第4期111-113,71,共4页
Computer Science
基金
国家自然科学基金(编号:19701006)
关键词
分布式网络
可靠度
因子分解算法
计算机网络
Distributed network, Imperfect node, Distributed program reliability, Factoring theorem, Algorithm complexity
