Abstract
Fault diagnosis of processors has played an essential role when evaluating the reliability of multiprocessor systems. In many novel multiprocessor systems, their diagnosability has been extensively explored. Conditional diagnosability is a useful measure for evaluating diagnosability by adding a further condition that all neighbors of every node in the system do not fail at the same time. In this paper, we study the conditional diagnosability of n-dimensional alternating group networks \(AN_n\) under the PMC model, and obtain the results \(t_c(AN_4)=5\), and \(t_c(AN_n)=6n-17\) for \(n\ge 5\). In addition, for the isomorphism property between \(AN_n\) and \(S_{n,k}\) with \(k=n-2\), namely \((n,n-2)\)-star graphs \(S_{n,n-2}\), the above results can be extended to \(S_{n,n-2}\), and we have \(t_c(S_{4,2})=5\) and \(t_c(S_{n,n-2})=6n-17\) for \(n\ge 5\). It is worth noting that the conditional diagnosability is about six times the degree of \(AN_n\) and \(S_{n,n-2}\), which is very different from general networks with a multiple of four.
Supported by the Ministry of Science and Technology in Taiwan.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Akers, S.B., Krishnamurthy, B.: A group-theoretic model for symmetric interconnection networks. IEEE Trans. Comput. 38(4), 555–566 (1989)
Akers, S.B., Krishnamurthy, B., Harel, D.: The star graph: an attractive alternative to the \(n\)-cube. In: Proceedings of the International Conference on Parallel Processing, pp. 393–400 (1987)
Chang, N.W., Cheng, E., Hsieh, S.Y.: Conditional diagnosability of Cayley graphs generated by transposition trees under the PMC model. ACM Trans. Des. Autom. Electron. Syst. 20(2) (2015). Article no. 20
Chang, N.W., Deng, W.H., Hsieh, S.Y.: Conditional diagnosability of \((n, k)\)-star networks under the comparison diagnosis model. IEEE Trans. Reliab. 64(1), 132–143 (2015)
Chang, N.W., Hsieh, S.Y.: Structural properties and conditional diagnosability of star graphs by using the PMC model. IEEE Trans. Parallel Distrib. Syst. 25(11), 3002–3011 (2014)
Chang, N.W., Hsieh, S.Y.: Conditional diagnosability of \((n, k)\)-star graphs under the PMC model. IEEE Trans. Dependable Secure Comput. 15(2), 207–216 (2018)
Cheng, E., Lipták, L., Qiu, K., Shen, Z.: On deriving conditional diagnosability of interconnection networks. Inf. Process. Lett. 112(17–18), 674–677 (2012)
Cheng, E., Qiu, K., Shen, Z.: A note on the alternating group network. J. Supercomput. 59(1), 246–248 (2012). https://doi.org/10.1007/s11227-010-0434-y
Chiang, W.K., Chen, R.J.: The \((n, k)\)-star graph: a generalized star graph. Inf. Process. Lett. 56(5), 259–264 (1995)
Dahbura, A.T., Masson, G.M.: An \(O(n^{2.5})\) fault identification algorithm for diagnosable systems. IEEE Trans. Comput. C–33(6), 486–492 (1984)
Duarte Jr., E.P., Ziwich, R.P., Albini, L.C.P.: A survey of comparison-based system-level diagnosis. ACM Comput. Surv. 43(3) (2011). article no. 22
Hao, R.X., Feng, Y.Q., Zhou, J.X.: Conditional diagnosability of alternating group graphs. IEEE Trans. Comput. 62(4), 827–831 (2013)
Hao, R.X., Zhou, J.X.: Characterize a kind of fault tolerance of alternating group network. Acta Mathematica Sinca Chinese Series 55(6), 1055–1066 (2012)
Hsu, G.H., Chiang, C.F., Shih, L.M., Hsu, L.H., Tan, J.J.M.: Conditional diagnosability of hypercubes under the comparison diagnosis model. J. Syst. Architect. 55(2), 140–146 (2009)
Ji, Y.: A class of Cayley networks based on the alternating groups. Adv. Math. (Chin.) 27(4), 361–362 (1998)
Jwo, J.S., Lakshmivarahan, S., Dhall, S.K.: A new class of interconnection networks based on the alternating group. Networks 23(4), 315–326 (1993)
Lai, P.L., Tan, J.J.M., Chang, C.P., Hsu, L.H.: Conditional diagnosability measures for large multiprocessor systems. IEEE Trans. Comput. 54(2), 165–175 (2005)
Lin, C.K., Tan, J.J.M., Hsu, L.H., Cheng, E., Lipták, L.: Conditional diagnosability of Cayley graphs generated by transposition trees under the comparison diagnosis model. J. Interconnection Netw. 9(1–2), 83–97 (2008)
Malek, M.: A comparison connection assignment for diagnosis of multiprocessor systems. In: Proceedings of the 7th International Symposium on Computer Architecture, pp. 31–35 (1980)
Preparata, F.P., Metze, G., Chien, R.T.: On the connection assignment problem of diagnosis systems. IEEE Trans. Electron. Comput. 16(12), 848–854 (1967)
Somani, A.K., Agarwal, V.K., Avis, D.: A generalized theory for system level diagnosis. IEEE Trans. Comput. C–36(5), 538–546 (1987)
Wang, S., Yang, Y.: The \(2\)-good-neighbor (\(2\)-extra) diagnosability of alternating group graph networks under the PMC model and MM* model. Appl. Math. Comput. 305, 241–250 (2017)
Zhang, Z., Xiong, W., Yang, W.: A kind of conditional fault tolerance of alternating group graphs. Inf. Process. Lett. 110(22), 998–1002 (2010)
Zhou, S.: The conditional fault diagnosability of \((n, k)\)-star graphs. Appl. Math. Comput. 218(19), 9742–9749 (2012)
Zhou, S., Xiao, W.: Conditional diagnosability of alternating group networks. Inf. Process. Lett. 110(10), 403–409 (2010)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Chang, NW., Hsieh, SY. (2020). A Survey for Conditional Diagnosability of Alternating Group Networks. In: Kim, D., Uma, R., Cai, Z., Lee, D. (eds) Computing and Combinatorics. COCOON 2020. Lecture Notes in Computer Science(), vol 12273. Springer, Cham. https://doi.org/10.1007/978-3-030-58150-3_52
Download citation
DOI: https://doi.org/10.1007/978-3-030-58150-3_52
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-58149-7
Online ISBN: 978-3-030-58150-3
eBook Packages: Computer ScienceComputer Science (R0)