g-Good-neighbor conditional diagnosability of star graph networks under PMC model and MM* model

Abstract

Diagnosability of a multiprocessor system is an important study topic. S. L. Peng, C. K. Lin, J. J. M. Tan, and L. H. Hsu [Appl. Math. Comput., 2012, 218(21): 10406–10412] proposed a new measure for fault diagnosis of the system, which is called the g-good-neighbor conditional diagnosability that restrains every fault-free node containing at least g fault-free neighbors. As a famous topological structure of interconnection networks, the n-dimensional star graph S_n has many good properties. In this paper, we establish the g-good-neighbor conditional diagnosability of S_n under the PMC model and MM∗ model.

Keywords

Interconnection network / graph / diagnosability / PMC model / MM∗ model / star graph

References

[1] AkersS B, KrishnamurthyB. A group-theoretic model for symmetric interconnection networks. IEEE Trans Comput, 1989, 38(4): 555–566

[2] BondyJ A, MurtyU S R. Graph Theory. New York: Springer, 2007

[3] ChangN W, HsiehS Y. Structural properties and conditional diagnosability of star graphs by using the PMC model. IEEE Trans Parallel Distrib Syst, 2014, 25(11): 3002–3011

[4] DahburaA T, MassonG M. An O(n2.5) fault identification algorithm for diagnosable systems. IEEE Trans Comput, 1984, 33(6): 486–492

[5] DayK, TriphthiA. A comparative study of topological properties of hypercubes and star graphs. IEEE Trans Parallel Distrib Syst, 1994, 5(1): 31–38

[6] HakimiS L, AminA T. Characterization of the connection assignment of diagnosable systems. IEEE Trans Comput, 1974, C-23: 86–88

[7] HsiehS Y. Embedding longest fault-free paths onto star graphs with more vertex faults. Theoret Comput Sci, 2005, 337(1-3): 370–378

[8] HuS C, YangC B. Fault tolerance on star graphs. In: Proceedings of the First Aizu International Symposium on Parallel Algorithms/Architecture Synthesis. 1995, 176–182

[9] HuangC W, HuangH L, HsiehS Y.Edge-bipancyclicity of star graphs with faulty elements. Theoret Comput Sci, 2011, 412: 6938–6947

[10] HungerfordW H. Algebra. New York: Springer-Verlag, 1974

[11] LaiP L, TanJ J M, ChangC P, HsuL H. Conditional diagnosability measures for large multiprocessor systems. IEEE Trans Comput, 2005, 54(2): 165–175

[12] LatifiS. A study of fault tolerance in star graph. Inform Process Lett, 2007, 102(5): 196–200

[13] LatifiS, SaberiniaE, WuX. Robustness of star graph network under link failure. Inform Sci, 2008, 178(3): 802–806

[14] LiT K, TanJ J M, HsuL H. Hyper Hamiltonian laceability on edge fault star graph. Inform Sci, 2004, 165(1-2): 59–71

[15] LiX J, XuJ M. Generalized measures for fault tolerance of star networks. Networks, 2014, 63(3): 225–230

[16] LiX Y, FanJ, LinC K, JiaX. Diagnosability evaluation of the data center network DCell. Comput J, 2017, 1–15,

[17] LinC K, TanJ J M, HsuL H, ChengE, Lipt´aakL. Conditional diagnosability of Cayley graphs generated by transposition trees under the comparison diagnosis model. J Inter Net, 2008, 9(1-2): 83–97

[18] MaengJ, MalekM. A comparison connection assignment for self-diagnosis of multiprocessor systems. In: Proceeding of 11th International Symposium on Fault-Tolerant Computing. 1981, 173–175

[19] PengS L, LinCK, TanJ J M, HsuLH. The g-good-neighbor conditional diagnosability of hypercube under PMC model. Appl Math Comput, 2012, 218(21): 10406–10412

[20] PretarataF P, MetzeG, ChienR T. On the connection assignment problem of diagnosable systems. IEEE Trans Comput, 1967, EC-16(6): 848–854

[21] RescignoA A. Vertex-disjoint spanning trees of the star network with applications to fault-tolerance and security. Inform Sci, 2001, 137(1-4): 259–276

[22] TsaiP Y, FuJ S, ChenJ H. Fault-free longest paths in star networks with conditional link faults. Theoret Comput Sci, 2009, 410(8-10): 766–775

[23] WalkerD, LatifiS. Improving bounds on link failure tolerance of the star graph. Inform Sci, 2010, 180(13): 2571–2575

[24] WanM, ZhangZ. A kind of conditional vertex connectivity of star graphs. Appl Math Lett, 2009, 22(2): 264–267

[25] WangM, YangW, GuoY, WangS. Conditional fault tolerance in a class of Cayley graphs. Int J Comput Math, 2016, 93(1): 67–82

[26] WangS, HanW. The g-good-neighbor conditional diagnosability of n-dimensional hypercubes under the MM∗ model. Inform Process Lett, 2016, 116: 574–577

[27] WangX, FanJ, ZhouJ, LinC K. The restricted h-connectivity of the data center network DCell. Discrete Appl Math, 2016, 203: 144–157

[28] YangY, WangS. Conditional connectivity of star graph networks under embedding restriction. Inform Sci, 2012, 199: 187–192

[29] YuanJ, LiuA, MaX, LiuX, QinX, ZhangJ. The g-good-neighbor conditional diagnosability of k-ary n-cubes under the PMC model and MM∗ model. IEEE Trans Parallel Distrib Syst, 2015, 26: 1165–1177

[30] ZhengJ, LatifiS, RegentovaE, LuoK, WuX. Diagnosability of star graphs under the comparison diagnosis model. Inform Process Lett, 2005, 93(1): 29–36

[31] ZhouS, LinL, XuL, WangD. The t/k-diagnosability of star graph networks. IEEE Trans Comput, 2015, 64(2): 547–555

[32] ZhouS, XuJ M. Fault diagnosability of arrangement graphs. Inform Sci, 2013, 246: 177–190

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag GmbH Germany