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

Abstract

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

CLC Number:

O157.5

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.

References

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.

[1]	HU Xiaochen, HE Weili, HAO Rongxia. Balanced judicious partitions of graphs with $\Delta($G$)-\delta($G$)\leq$2 [J]. Operations Research Transactions, 2015, 19(1): 108-116.
[2]	SUN Lin, LUO Zhaoyang. Edge colourings of embedded special graphs [J]. Operations Research Transactions, 2015, 19(1): 125-130.
[3]	LIN Yishu, LIU Yan. Bandwidth sum with an edge added [J]. Operations Research Transactions, 2014, 18(4): 105-110.
[4]	CHEN Lin, HUANG Qiongxiang. Tricyclic graphs with exactly two Q-main eigenvalues [J]. Operations Research Transactions, 2014, 18(3): 13-32.
[5]	DING Lushun, WANG Guanghui, YAN Jin. The properly colored paths and cycles for the triangle-free graphs [J]. Operations Research Transactions, 2014, 18(3): 116-120.
[6]	DUAN Huiming, ZENG Bo, DOU Zhi. On connected three multiply K_{n}-residual graphs [J]. Operations Research Transactions, 2014, 18(2): 59-68.
[7]	OUYANG Zhangdong, HUANG Yuanqiu. On the crossing number of products of K_3,3 with S_n [J]. Operations Research Transactions, 2014, 18(2): 69-76.
[8]	SHAN Erfang, YE Tingting. Clique-coloring numbers of some product graphs [J]. Operations Research Transactions, 2013, 17(4): 103-108.
[9]	MA Gang, MA Xiaomin, YE Jianhua, MA Shaoxian. Some conclusions of vertex-distinguishing edge coloring of product graph [J]. Operations Research Transactions, 2013, 17(3): 108-114.
[10]	ZHOU Zhidong,WANG Jing. On the crossing numbers of W₆*S_n [J]. Operations Research Transactions, 2013, 17(2): 10-18.

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 10

Recommended Articles

Metrics

Comments