Diagnosability of interconnection networks: past, present and future

References

• Cheng E, Qiu K, Shen Z. On diagnosability of interconnection networks. Int J Unconvent Comput. 2017;13:245–251.
   Web of Science ®Google Scholar
• Harary F, Hayes JP, Wu H-J. A survey of the theory of hypercube graphs. Comput Math Appl. 1988;15(4):277–289.
   Web of Science ®Google Scholar
• Akers SB, Krishnamurthy B. A group theoretic model for symmetric interconnection networks. IEEE Trans Comput. 1989;38(4):555–566.
   Web of Science ®Google Scholar
• Chou ZT, Hsu CC, Sheu JP. Bubblesort star graphs: a new interconnection network. Proceedings of 1996 International Conference on Parallel and Distributed Systems; Tokyo, Japan, June 3-6, 1996. IEEE Computer Society press. p. 41–48.
   Google Scholar
• Day K, Tripathi A. Arrangement graphs: A class of generalized star graphs. Inf Process Lett. 1992;42:235–241.
   Web of Science ®Google Scholar
• Chiang W-K, Chen R-J. The (n,k)-star graph: a generalized star graph. Inf Process Lett. 1995;56:259–264.
   Web of Science ®Google Scholar
• Hakimi SL, Amin AT. Characterization of connection assignment of diagnosable systems. IEEE Trans Comput. 1974;23(1):86–88.
   Web of Science ®Google Scholar
• Preparata FP, Metze G, Chien RT. On the connection assignment problem of diagnosable systems. IEEE Trans Electron Comput. 1967;EC-16(6):848–854.
   Google Scholar
• Cheng E, Liptak L, Qiu K, et al. On deriving conditional diagnosability of interconnection networks. Inf Process Lett. 2012;112:674–677.
   Web of Science ®Google Scholar
• Hong W-S, Hsieh S-Y. Strong diagnosability and conditional diagnosability of augmented cubes under the comparison diagnosis model. IEEE Trans Reliab. 2012;61:140–148.
   Web of Science ®Google Scholar
• Lai P-L, Tan JJM, Chang C-P, et al. Conditional diagnosability measures for large multiprocessor systems. IEEE Trans Comput. 2005;54:165–175.
   Web of Science ®Google Scholar
• Peng SL, Lin CK, Tan JJM, et al. The g-good-neighbor conditional diagnosability of hypercube under the PMC model. Appl Math Comput. 2012;218(21):10406–10412.
   Web of Science ®Google Scholar
• Zhang S, Yang W. The g-extra conditional diagnosability and sequential t/k-diagnosability of hypercubes. Int J Comput Math. 2016;93:482–497.
   Web of Science ®Google Scholar
• Cheng E, Hao R-X, Qiu K. Structural properties and fault resiliency of interconnection networks. In: Adamatzky A, Akl S, Sirakoulis G, editors. Parallel to emergent computing. CRC Press; 2019. Boca Raton, FL; p. 77–101.
   Google Scholar
• Maeng J, Malek M. A comparison connection assignment for self-diagnosis of multiprocessor systems. Proceedings to The 11th International Symposium on Fault-Tolerant Computing; 1981. La Baule, USA. p. 173–175.
   Google Scholar
• Malek M. A comparison connection assignment for diagnosis of multiprocessor systems. Proceedings to The 7th International Symposium on Computer Architecture; 1980. La Baule, USA. p. 31–35.
   Google Scholar
• Sengupta A, Dahbura AT. On self-diagnosable multiprocessor systems: diagnosis by the comparison approach. IEEE Trans Comput. 1992;41:1386–1396.
   Web of Science ®Google Scholar
• Dahbura AT, Masson GM. An n2.5 faulty identification algorithm for diagnosable systems. IEEE Trans Comput. 1984;33(6):486–492.
   Web of Science ®Google Scholar
• Stephens J, Raghavan V. On single-fault set diagnosability in the PMC model. IEEE Trans Comput. 1993;42:981–983.
   Web of Science ®Google Scholar
• Sullivan GF. A polynomial time algorithm for fault diagnosability. Proceedings to 25th Annual Symposium of Foundations Computer Science. IEEE Computer Society; 1984. p. 148–156.
   Google Scholar
• Zhu Q. On conditional diagnosability and reliability of the BC networks. J Supercomput. 2008;45:173–184.
   Web of Science ®Google Scholar
• Barsi F, Grandoni F, Maestrini P, et al. A theory of diagnosability of digital systems. IEEE Trans Comput. 1976;C-25(6):585–593.
   Web of Science ®Google Scholar
• Fan J. Diagnosability of crossed cubes under the comparison diagnosis model. IEEE Trans Parallel Distrib Syst. 2002;13:1099–1104.
   Web of Science ®Google Scholar
• Fan J. Diagnosability of the mobius cube. IEEE Trans Parallel Distrib Syst. 1998;9:923–928.
   Web of Science ®Google Scholar
• Wang D. Diagnosability of hypercubes and enhanced hyper-cubes under the comparison diagnosis model. IEEE Trans Comput. 1999;48:1369–1374.
   Web of Science ®Google Scholar
• Zheng J, Latifi S, Regentova E, et al. Diagnosability of star graphs under the comparison diagnosis model. Inf Process Lett. 2005;93:29–36.
   Web of Science ®Google Scholar
• Chang C-P, Lai P-L, Tan J-MT, et al. Diagnosability of t-connected networks and product networks under the comparison diagnosis model. IEEE Trans Comput. 2004;53:1582–1590.
   Web of Science ®Google Scholar
• Chang G-Y, Chang GJ, Chen G-H. Diagnosabilities of regular networks. IEEE Trans Parallel Distrib Syst. 2005;16:314–323.
   Web of Science ®Google Scholar
• Angjeli A, Cheng E, Lipták L. Linearly many faults in dual-cube-like networks. Theor Comput Sci. 2013;472:1–8.
   Web of Science ®Google Scholar
• Chang N-W, Lin T-Y, Hsieh S-Y. Conditional diagnosability of k-ary n-cubes under the PMC model. ACM Trans Des Autom Electron Syst. 2012;17:46–60.
   Web of Science ®Google Scholar
• Chang N, Cheng E, Hsieh S-Y. Conditional diagnosability of Cayley graphs generated by transposition trees under the PMC model. ACM Trans Des Autom Electron Syst. 2015;20: Article No. 20.
   Web of Science ®Google Scholar
• Cheng E, Qiu K, Shen Z. Connectivity results of complete cubic network as associated with linearly many faults. J Interconnect Netw. 2015;15(1 & 2):1550007 (23 pages).
   Web of Science ®Google Scholar
• Cheng E, Qiu K, Shen Z. Structural properties of the generalized exchanged hypercubes. In: Adamatzky A, editor. Emergent computation: emergence, complexity, computation. Vol. 24. Cham: Springer; 2017. p. 215–232.
   Google Scholar
• Guo J, Lu M. Conditional diagnosability of the SPn graphs under the comparison diagnosis model. Appl Math Comput. 2018;336:249–256.
   Web of Science ®Google Scholar
• Hsu G-H, Chiang C-F, Shih L-M, et al. Conditional diagnosability of hypercubes under the comparison diagnosis model. J Syst Archit. 2016;55:21–29.
   Google Scholar
• Lin C-K, Tan JJM, Hsu L-H, et al. Conditional diagnosability of Cayley graphs generated by transposition trees under the comparison diagnosis model. J Interconnect Netw. 2008;9:83–97.
   Google Scholar
• Xu M, Thulasiraman K, Hu X-D. Conditional diagnosability of matching com-position networks under the PMC model. IEEE Trans Circuits Syst. 2009;1156:875–879.
   Google Scholar
• Zhou S, Xiao W. Conditional diagnosability of alternating group networks. Inf Process Lett. 2010;110:403–409.
   Web of Science ®Google Scholar
• Cheng E, Qiu K, Shen Z. A general approach to deriving the g-good-neighbor conditional diagnosability of interconnection networks. Theor Comput Sci. 2019;757(24):56–67.
   Google Scholar
• Gu M-M, Hao R-X, Yang D-X. A short note on the 1, 2-good-neighbor diagnosability of balanced hypercubes. J Interconnect Netw. 2016;16(2):1650001 (12 pages).
   Web of Science ®Google Scholar
• Xu X, Li W-W, Zhou S-M, et al. The g-good-neighbor diagnosability of (n,k)-star graph. Theor Comput Sci. 2017;659:53–63.
   Web of Science ®Google Scholar
• Wang M, Guo Y, Wang S. The 1-good-neighbour diagnosability of Cayley graphs generated by transposition trees under the PMC model and MM* model. Int J Comput Math. 2017;94:620–631.
   Web of Science ®Google Scholar
• Wang S, Ren Y. g-good-neighbor diagnosability of arrangement graphs under the PMC model and MM* model. Information. 2018;9:275. doi: 10.3390/info9110275
   Google Scholar
• Wang S, Wang M. The g-good-neighbor and g-extra diagnosability of networks. Theor Comput Sci. 2019;773(14):107–114.
   Google Scholar
• Yuan J, Liu A, Ma X, et al. The g-good-neighbor conditional diagnosability of k-Ary n-Cubes under the PMC model and MM* model. Int J Parallel Emergent Distrib Syst. 2015;26(4):1165–1177.
   Google Scholar
• Wang S, Wang Z, Wang M. The 2-extra connectivity and 2-extra diagnosability of bubble-sort star graph networks. Comput J. 2016;59(12):1839–1856.
   Web of Science ®Google Scholar
• Lv MJ, Zhou SM, Sun XL, et al. Reliability of (n,k)-star network based on g -extra conditional fault. Theor Comput Sci. 2019;757:44–55.
   Web of Science ®Google Scholar
• Liu HQ, Zhang SZ, Li D. On g-extra conditional diagnosability of hierarchical cubic networks. Theor Comput Sci. 2019. doi: 10.1016/j.tcs.2019.04.028
   Web of Science ®Google Scholar
• Zhu Q, Zhang J, Li LL. The h-extra connectivity and h-extra conditional diagnosability of bubble-sort star graphs. Discrete Appl Math. 2018;251:173–184.
   Web of Science ®Google Scholar
• Stewart I. A general technique to establish the asymptotic conditional diagnosability of interconnection networks. Theor Comput Sci. 2012;452:132–147.
   Web of Science ®Google Scholar
• Cheng E, Liptak L, Qiu K, et al. A unified approach to the conditional diagnosability of interconnection networks. J. Interconnect Netw. 2012;13:1250007 (19 pages).
   Google Scholar
• Cheng E, Qiu K, Shen Z. On the conditional diagnosability of matching composition networks. Theor Comput Sci. 2014;557:101–114.
   Web of Science ®Google Scholar
• Lin L, Xu L, Zhou S. Relating the extra connectivity and the conditional diagnosability of regular graphs under the comparison model. Theor Comput Sci. 2008;618:83–97.
   Google Scholar
• Yang M-C. Conditional diagnosability of matching composition networks under the MM* model. Inf Sci. 2013;233:230–243.
   Web of Science ®Google Scholar
• Cheng D. A relationship between g-good-neighbour conditional diagnosability and g-good-neighbour connectivity in regular graphs. Int J Comput Math. 2018;3(1):47–52.
   Google Scholar
• Cheng E, Liptak L. Diagnosability of Cayley graphs generated by transposition trees with missing edges. Inf Sci. 2013;238:250–252.
   Web of Science ®Google Scholar
• Cheng E, Liptak L, Steffy D. Strong local diagnosability of (n,k)-star graphs and Cayley graphs generated by 2-trees with missing edges. Inf Process Lett. 2013;113:452–456.
   Web of Science ®Google Scholar
• Chiang C-F, Hsu G-H, Shih L-M, et al. Diagnosability of star graphs with missing edges. Inf Sci. 2012;188:253–259.
   Web of Science ®Google Scholar
• Gu M-M, Hao R-X. The pessimistic diagnosability of three kinds of graphs. Discrete Appl Math. 2017;217:548–556.
   Web of Science ®Google Scholar
• Somani AK, Peleg O. On diagnosability of large fault sets in regular topology-based computer systems. IEEE Trans Comput. 1996;45:892–903.
   Web of Science ®Google Scholar
• Cheng E, Liptak L. Structural properties of Cayley graphs generated by transposition trees. Congr Numer. 2006;180:81–96.
   Google Scholar
• Cheng E, Liptak L. Fault resiliency of Cayley graphs generated by transpositions. Int J Found Comput Sci. 2007;18:1005–1022.
   Web of Science ®Google Scholar
• Cheng E, Liptak L. Linearly many faults in Cayley graphs generated by transposition trees. Inf Sci. 2007;177:4877–4882.
   Web of Science ®Google Scholar
• Cheng E, Liptak L, Yang W, et al. A kind of conditional vertex connectivity of Cayley graphs generated by 2-trees. Inf Sci. 2011;181:4300–4308.
   Web of Science ®Google Scholar
• Cheng E, Lipták L, Yuan A. Linearly many faults in arrangement graphs. Networks. 2013;61:281–289.
   Web of Science ®Google Scholar
• Cheng E, Qiu K, Shen Z. A strong connectivity property of the generalized exchanged hypercube. Discrete Appl Math. 2017;216:529–536.
   Web of Science ®Google Scholar
• Hsu L-H, CQS E, Lipták L, et al. Component connectivity of the hypercubes. Int J Comput Math. 2012;89(2):137–145.
   Web of Science ®Google Scholar
• Li X-J, Xu J-M. Generalized measures of fault tolerance in exchanged hypercubes. Inf Process Lett. 2013;113:533–537.
   Web of Science ®Google Scholar
• Li X-J, Xu J-M. Fault-tolerance of (n,k)-star networks. Appl Math Comput. 2014;248(1):525–530.
   Google Scholar
• Ma M. The connectivity of exchanged hypercubes. Discrete Math Algorithms Appl. 2010;2:213–220.
   Google Scholar
• Ma M, Zhu L. The superconnectivity of exchanged hypercubes. Inf Process Lett. 2011;111:360–364.
   Web of Science ®Google Scholar
• Oh AD, Choi H-A. Generalized measures of fault tolerance in n-cube networks. IEEE Trans Parallel Distrib Syst. 1993;4:702–703.
   Web of Science ®Google Scholar
• Wu J, Guo G. Fault tolerance measures for m-ary n-dimensional hypercubes based on forbidden faulty sets. IEEE Trans Comput. 1998;47:888–893.
   Web of Science ®Google Scholar
• Yang X, Evans DJ, Megson GM. On the maximal connected component of a hypercube with faulty vertices. Int J Comput Math. 2004;81(5):515–525.
   Web of Science ®Google Scholar
• Yang X, Evans DJ, Megson GM. On the maximal connected component of a hypercube with faulty vertices II. Int J Comput Math. 2004;81(10):1175–1185.
   Web of Science ®Google Scholar
• Yang X, Evans DJ, Megson GM. On the maximal connected component of a hypercube with faulty vertices III. Int J Comput Math. 2006;83(1):27–37.
   Web of Science ®Google Scholar
• Yang W, Li H, Guo X. A kind of conditional fault tolerance of (n,k)-star graphs. Inf Process Lett. 2010;110:1007–1011.
   Web of Science ®Google Scholar
• Yuan A, Cheng E, Liptak L. Linearly many faults in arrangement graphs. Networks. 2013;61(4):281–289.
   Web of Science ®Google Scholar
• Yuan A, Cheng E, Liptak L. Linearly many faults in (n,k)-star graphs. Int J Found Comput Sci. 2011;22(7):1729–1745.
   Web of Science ®Google Scholar
• Zhou JX. On g-extra connectivity of hypercube-like networks. J Comput Syst Sci. 2017;88:208–219.
   Web of Science ®Google Scholar
• Zhou S, Xu J-M. Conditional fault tolerance of arrangement graphs. Inf Process Lett. 2011;111:1037–1043.
   Web of Science ®Google Scholar
• Cheng E, Qiu K, Shen Z. On the restricted connectivity of the arrangement graphs. J Supercomput. 2017;73:3669–3682.
   Web of Science ®Google Scholar
• Xu L, Lin L, Zhou S, et al. The extra Connectivity, extra conditional diagnosability, and t/m-diagnosability of arrangement graphs. IEEE Trans Reliab. 2016;65(3):1–15.
   Web of Science ®Google Scholar