×

Fault tolerance in \(k\)-ary \(n\)-cube networks. (English) Zbl 1252.68044

Summary: The \(k\)-ary \(n\)-cube \(Q^k_n\) is one of the most commonly used interconnection topologies for parallel and distributed computing systems. Let \(f(n,m)\) be the minimum number of faulty nodes that make every \((n - m)\)-dimensional subcube \(Q^k_{n-m}\) faulty in \(Q^k_n\) under node-failure models. In this paper, we prove that \(f(n, 0)=1\), \(f(n, 1)=k\) for odd \(k \geq 3\), \(f(n,n - 1) = k^{n - 1}\) for odd \(k \geq 3\), and \(k^m \leq f (n,m) \leq {n-1 \choose m-1}k^m - {n-2 \choose m-1}k^{m-1}\) for odd \(k \geq 3\).

MSC:

68M15 Reliability, testing and fault tolerance of networks and computer systems
68R10 Graph theory (including graph drawing) in computer science
68M10 Network design and communication in computer systems
Full Text: DOI

References:

[1] Ashir, Yaagoub A.; Stewart, Iain A., Fault-tolerant embeddings of Hamiltonian circuits in \(k\)-ary \(n\)-cubes, SIAM Journal on Discrete Mathematics, 15, 3, 317-328 (2002) · Zbl 1018.68058
[2] Bernd Becker, Hans-Ulrich Simon, How robust is the \(n\); Bernd Becker, Hans-Ulrich Simon, How robust is the \(n\) · Zbl 0647.68007
[3] Bondy, J. A.; Murty, U. S.R., Graph Theory (2008), Springer: Springer New York · Zbl 1134.05001
[4] Brualdi, Richard A., Introductory Combinatorics (1999), Prentice Hall: Prentice Hall New Jersey · Zbl 0915.05001
[5] Chan, Mee Yee; Lee, Shiang-Jen, On the existence of Hamiltonian circuits in faulty hypercubes, SIAM Journal on Discrete Mathematics, 4, 4, 511-527 (1991) · Zbl 0747.05035
[6] Fu, Jung-Sheng, Fault-free Hamiltonian cycles in twisted cubes with conditional link faults, Theoretical Computer Science, 407, 1-3, 318-329 (2008) · Zbl 1154.68034
[7] Ho, Tung-Yang; Sung, Ting-Yi; Hsu, Lih-Hsing, A note on edge fault tolerance with respect to hypercubes, Applied Mathematics Letters, 18, 10, 1125-1128 (2005) · Zbl 1091.68010
[8] Hsieh, Sun-Yuan, Embedding longest fault-free paths onto star graphs with more vertex faults, Theoretical Computer Science, 337, 1-3, 370-378 (2005) · Zbl 1104.68085
[9] R.E. Kessler, J.L. Schwarzmeier, Cray T3D: a new dimension for Cray Research, in: Proceedings of the 38th IEEE Computer Society International Conference, Compcon Spring’93, San Francisco, CA, 1993, pp. 176-182.; R.E. Kessler, J.L. Schwarzmeier, Cray T3D: a new dimension for Cray Research, in: Proceedings of the 38th IEEE Computer Society International Conference, Compcon Spring’93, San Francisco, CA, 1993, pp. 176-182.
[10] Latifi, Shahram, A study of fault tolerance in star graph, Information Processing Letters, 102, 5, 196-200 (2007) · Zbl 1184.68115
[11] Lin, Shangwei; Wang, Shiying; Li, Chunfang, Panconnectivity and edge-pancyclicity of \(k\)-ary \(n\)-cubes with faulty elements, Discrete Applied Mathematics, 159, 4, 212-223 (2011) · Zbl 1214.68087
[12] Ma, Meijie; Liu, Guizhen; Xu, Jun-Ming, Fault-tolerant embedding of paths in crossed cubes, Theoretical Computer Science, 407, 1-3, 110-116 (2008) · Zbl 1152.68010
[13] Noakes, Michael; Dally, William J., System design of the \(J\)-machine, (Proceedings of the Sixth MIT Conference on Advanced Research in VLSI (1990), MIT Press: MIT Press Cambridge, MA), 179-194
[14] Peterson, Craig; Sutton, James; Wiley, Paul, iWarp: a 100-MOPS, LIW microprocessor for multicomputers, IEEE Micro, 11, 3, 26-29 (1991), 81-87
[15] Stewart, Iain A.; Xiang, Yonghong, Embedding long paths in \(k\)-ary \(n\)-cubes with faulty nodes and links, IEEE Transactions on Parallel and Distributed Systems, 19, 8, 1071-1085 (2008)
[16] Tsai, Ping-Ying; Fu, Jung-Sheng; Chen, Gen-Huey, Fault-free longest paths in star networks with conditional link faults, Theoretical Computer Science, 410, 8-10, 766-775 (2009) · Zbl 1162.68004
[17] Wang, Shiying; Yang, Yuxing, Fault tolerance in bubble-sort graph networks, Theoretical Computer Science, 421, 62-69 (2012) · Zbl 1232.68024
[18] Yang, Ming-Chien; Tan, Jimmy J. M.; Hsu, Lih-Hsing, Hamiltonian circuit and linear array embeddings in faulty \(k\)-ary \(n\)-cubes, Journal of Parallel and Distributed Computing, 67, 4, 362-368 (2007) · Zbl 1115.68032
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.