计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (21): 129-131.DOI: 10.3778/j.issn.1002-8331.2009.21.038

• 理论科学研究 • 上一篇    下一篇

煎饼网路的容错性能研究

周书明   

  1. 福建师范大学 数学与计算机科学学院,福州 350007
  • 收稿日期:2009-05-04 修回日期:2009-06-04 出版日期:2009-07-21 发布日期:2009-07-21
  • 通讯作者: 周书明

Study of fault tolerance on pancake networks

ZHOU Shu-ming   

  1. College of Mathematics and Computer Science,Fujian Normal University,Fuzhou 350007,China
  • Received:2009-05-04 Revised:2009-06-04 Online:2009-07-21 Published:2009-07-21
  • Contact: ZHOU Shu-ming

摘要: 随着多处理机系统规模的不断扩大,其组件的脆弱性也随着增大。最大连通分支的可能包含的最少节点数可作为评估网络容错性能的一种测度,也可以看做是传统的连通度度量的一个补充。在故障节点较多而使得残存网络不连通时,为了对网络有一个整体的评价,有必要估计最大连通分支的规模。分析煎饼网络Pn的容错性,并证明其在故障节点总数|F|≤kn-3k+1(k=2,3)时,最大连通分支的节点数不少于n!-|F|-(k-1),而剩余部分的节点总数不超过k-1。

Abstract: The growing size of the multiprocessor system increases its vulnerability to component failures.The minimum size of a largest connected component can be regarded as a measure of fault tolerance of the network,which provides a complement to the vertex connectivity.In order to make a full evaluation,it is essential to estimate the minimum size of a largest connected component providing a lot of failing processors(vertices) which yield a disconnected surviving network.This paper analyses the fault tolerance of Pancake network,and shows that if F is a set of vertices in Pn with |F|≤kn-3k+1(k=2,3),Pn-F has one largest connected component with at least n!-|F|-(k-1) vertices,and the remaining small components have at most k-1 vertices in total.