Pancake网络的t/k-诊断度及其算法

运筹学学报 ›› 2014, Vol. 18 ›› Issue (4): 65-77.

Pancake网络的t/k-诊断度及其算法

宋苏琳¹, 林丽美¹, 周书明^1,2,*

1. 福建师范大学数学与计算机科学学院, 福州 350007; 2. 福建师范大学网络安全与密码技术重点实验室, 福州 350007

收稿日期:2014-04-09 出版日期:2014-12-15 发布日期:2014-12-15
通讯作者: 周书明 E-mail:zhoushuming@fjnu.edu.cn
基金资助:
福建省教育厅A类基金(No. JA12073), 福建省自然科学基金(No. 2013J01221), 福建师范大学“网络与信息安全关键理论和技术”校创新团队(No. IRTL1207)

The t/k-diagnosability and diagnosis algorithm of Pancake networks

SONG Sulin¹, LIN Limei¹, ZHOU Shuming^1,2,*

1. School of Mathematics and Computer Science, Fujian Normal University, Fuzhou 350007, China; 2. Fujian Provincial Key Laboratory of Network Security and Cryptology, Fujian Normal University, Fuzhou 350007, China

Received:2014-04-09 Online:2014-12-15 Published:2014-12-15

摘要/Abstract

摘要： 由于大型多处理机系统规模的不断扩大, 其组件脆弱性也随之增加, 因此故障容错性能对于多处理机系统尤为重要. t/k-诊断分析是一种能极大提高多处理机系统自我诊断性能的系统级故障诊断策略，该诊断策略能识别至多t个故障处理机节点, 其中可能包含至多$k$个被误诊的处理机. 首先给出了Pancake网络P_n(n\geq 5) 的容错性分析, 其后证明了P_n在PMC模型下是((k+1)n-3k-1)/k-可诊断的, 其中1\leq k\leq 3, 最后还给出复杂度为O(NlogN)的快速诊断算法来识别所有的故障节点.

关键词: Pancake网络, 容错性, t/k-诊断度, 诊断算法

Abstract: Fault tolerance is especially important for multiprocessor system since the growing size of the multiprocessor system increases its vulnerability to component failures. The t/k-diagnosis is a kind of diagnostic strategy at system level that can significantly enhance the multiprocessor system's self-diagnosing capability. It can detect up to t faulty processors (or nodes, units) which might include at most k misdiagnosed processors. This paper first explores the fault tolerance of Pancake networks P_n (n\geq 5), and then proves that P_n is ((k+1)n-3k-1)/k-diagnosable under the PMC model, 1\leq k\leq 3 Finally it proposes a quick diagnosis algorithm with complexity O(NlogN) to identify all the faulty nodes.

Key words: Pancake networks, fault tolerance, t/k-diagnosability, diagnosis algorithm

中图分类号:

O157.5

宋苏琳, 林丽美, 周书明. Pancake网络的t/k-诊断度及其算法[J]. 运筹学学报, 2014, 18(4): 65-77.

SONG Sulin, LIN Limei, ZHOU Shuming. The t/k-diagnosability and diagnosis algorithm of Pancake networks[J]. Operations Research Transactions, 2014, 18(4): 65-77.

参考文献

Preparata F P, Metze G, Chen R T. On the connection assignment problem of diagnosable systems [J]. IEEE Transactions on Electronic Computers, 1967, EC-16: 848-854.

Somani A K, Peleg O. On diagnosability of large fault sets in regular topology-based computer systems [J]. IEEE Transactions on Computers, 1996, 45(8): 892-903.

Fan J, Lin X. The t/k-diagnosability of the BC graphs [J]. IEEE Transactions on Computers, 2005, 54(2): 176-184.

Yang W, Liu H, Qin C. On the t/k-diagnosability of BC Networks [J]. Applied Mathematics and Computation, 2013, 225: 366-371.
Yang W, Liu H, Qin C. On the t/k-diagnosability of BC Networks [J]. Applied Mathematics and Computation, 2013, 225: 366-371.

Zhou S, Lin L, Xu L, et al. The t/k-diagnosability of star graph networks [EB/OL]. [2014-10-20]. http://doi.ieeecomputersociety.org/10.1109/TC.2013.228.

Xu J M. Combinatorial Theory in Networks [M]. Beijing: Science Press, 2013.

Akers S B, Krishnamurthy B. A group-theoretic model for symmetric interconnection networks [J]. IEEE Transaction on Computers, 1989, 38(4): 555-566.

Gates W H, Papadimitriou C H. Bounds for sorting by prefix reversal [J]. Discrete Mathematics, 1979, 27: 47-49.

Cibulka J. On average and highest number of flips in pancake sorting [J]. Theoretical Computer Science, 2011, 412: 822-834.

Kanevsky A, Feng C. On the embedding of cycles in pancake graphs [J]. Parallel Computing, 1995, 21(6): 923-936.

Lin C K, Huang H M, Hsu L H. The super connectivity of the pancake graphs and the super laceability of the star graphs [J]. Theoretical Computer Science, 2005, 339: 251-257.

Suzuki Y, Kaneko K. An algorithm for node-disjoint paths in pancake graphs [J]. IEICE Transactions on Information and Systems, 2003, E86-D(3): 610-615.

Kaneko K. Hamiltonian cycles and hamiltonian paths in faulty burnt pancake graphs [J]. IEICE Transactions on Information and Systems, 2007, E90-D(4): 716-721.

Kaneko K. An algorithm for node-to-set disjoint paths problem in burnt pancake graphs [J]. IEICE Transactions on Information and Systems, 2003, E86-D(12): 2588-2594.

Iwasaki T, Kaneko K. Fault-tolerant routing in burnt pancake graphs [J]. Information Processing Letters, 2010, 110: 535-538.

Chin C, Weng T H, Hsu L H, et al. The spanning connectivity of the burnt pancake graphs [J]. IEICE Transactions on Information and Systems, 2009, E92-D(3): 389-400.

Cheng E, Lu D, Xu B. Strong matching preclusion of pancake graphs [J]. Journal of Interconnection Networks, 2013, 14(2): 1-14.

Chen Y C, Tan J J M. Restricted connectivity for three families of interconnection networks [J]. Applied Mathematics and Computation, 2007, 188(2): 1848-1855.

周书明. 煎饼网络的容错性能研究 [J]. 计算机工程与应用, 2009, 45(21): 129-131.

Zhou S, Xu L. Conditional fault diagnosability of pancake graphs [J]. Journal of Convergence Information Technology, 2013, 8: 668-675.

Yang X. A fast pessimistic one-step diagnosis algorithm for hypercube multicomputer systems [J]. Journal of Parallel and Distributed Computing, 2004, 64(4): 546-553.

Yang X, Tang Y. A (4n-9)/3 diagnosis algorithm on n-dimensional cube network [J]. Information Sciences, 2007, 177(8): 1771-1781.

Zhou S, Xu J M. Fault diagnosability of arrangement graphs [J]. Information Sciences, 2013, 246: 177-190.

Zhou S. The conditional fault diagnosability of (n,k)-star graphs [J]. Applied Mathematics and Computation, 2012, 218: 9742-9749.