Pancake graphs: structural properties and conditional diagnosability. (English) Zbl 07610128
Summary: Because of the increasing size of multi-processor systems, processor-fault diagnosis has played critical role in measuring reliability. The diagnosability of numerous well-known multiprocessor systems has been widely investigated. The conditional diagnosability is a new measure of diagnosability by restricting an additional condition under which any fault set cannot contain all the neighbors of any node in a system. This study evaluated the conditional diagnosability for pancake graphs in the PMC model. First, several properties of pancake graphs were derived and, based on these properties, the conditional diagnosability of an \(n\)-dimensional pancake graph was shown to be 2 for \(n=3\) and \(8n-21\) for \(n\ge 4\).
MSC:
| 68Mxx | Computer system organization |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
Keywords:
interconnection networks; PMC diagnosis model; conditional diagnosability; pancake graphs; fault tolerance; multiprocessor systemsReferences:
| [1] | Akers, SB; Krishnamurthy, B., A group-theoretic model for symmetric interconnection networks, IEEE Trans Comput, 38, 4, 555-566 (1989) · Zbl 0678.94026 · doi:10.1109/12.21148 |
| [2] | Armstrong, JR; Gray, FG, Fault diagnosis in a boolean \(n\) cube array of multiprocessors, IEEE Trans Comput, 30, 8, 587-590 (1981) · Zbl 0461.94023 · doi:10.1109/TC.1981.1675844 |
| [3] | Chang, GY; Chang, GJ; Chen, GH, Diagnosabilities of regular networks, IEEE Trans Parallel Distrib Syst, 16, 4, 314-323 (2005) · doi:10.1109/TPDS.2005.44 |
| [4] | Chang, NW; Hsieh, SY, Conditional diagnosability of augmented cubes under the PMC model, IEEE Trans Dependable Secure Comput, 9, 1, 46-60 (2012) · doi:10.1109/TDSC.2010.59 |
| [5] | Chang, NW; Hsieh, SY, Structural properties and conditional diagnosability of star graphs by using the PMC model, IEEE Trans Parallel Distrib Syst, 25, 11, 3002-3011 (2014) · doi:10.1109/TPDS.2013.290 |
| [6] | Chang, NW; Lin, TY; Hsieh, SY, Conditional diagnosability of \(k\)-ary \(n\)-cubes under the PMC model, ACM Trans Des Autom Electron Syst, 17, 4 (2012) · doi:10.1145/2348839.2348850 |
| [7] | Chang NW, Wu HJ, Hsieh SY (2021) “A study for conditional diagnosability of pancake graphs” In: Proceedings of the 27th International Conference, COCOON 2021, Tainan, Taiwan, October 24-26, Lecture Notes in Computer Science: Computing and Combinatorics 13025, pp 298-305 · Zbl 07670471 |
| [8] | Chen, CA; Hsieh, SY, \(t/t\)-Diagnosability of regular graphs under the PMC model, ACM Trans Des Autom Electron Syst (TODAES), 18, 2 (2013) |
| [9] | Cheng, E.; Lipman, MJ, On deriving conditional diagnosability of interconnection networks, Inf Process Lett, 112, 17-18, 674-677 (2012) · Zbl 1248.68105 · doi:10.1016/j.ipl.2012.06.008 |
| [10] | Dahbura, AT; Masson, GM, An \(O(n^{2.5})\) fault identification algorithm for diagnosable systems, IEEE Trans Comput, 33, 6, 486-492 (1984) · Zbl 0537.68043 · doi:10.1109/TC.1984.1676472 |
| [11] | Hong, WS; Hsieh, SY, Strong diagnosability and conditional diagnosability of augmented cubes under the comparison diagnosis model, IEEE Trans Reliab, 61, 1, 140-148 (2012) · doi:10.1109/TR.2011.2170105 |
| [12] | Hsieh, SY; Chen, YS, Strongly diagnosable product networks under the comparison diagnosis model, IEEE Trans Comput, 57, 6, 721-732 (2008) · Zbl 1373.68136 · doi:10.1109/TC.2008.30 |
| [13] | Hsieh, SY; Chen, YS, Strongly diagnosis systems under the comparison diagnosis model, IEEE Trans Comput, 57, 12, 1720-1725 (2008) · Zbl 1368.68079 · doi:10.1109/TC.2008.104 |
| [14] | Hsieh, SY; Chuang, TY, The strong diagnosability of regular networks and product networks under the PMC model, IEEE Trans Parallel Distrib Syst, 62, 4, 839-843 (2013) · Zbl 1365.68085 |
| [15] | Hsieh, SY; Kao, CY, The conditional diagnosability of \(k\)-ary \(n\)-cubes under the comparison diagnosis model, IEEE Trans Comput, 62, 4, 839-843 (2013) · Zbl 1365.68085 · doi:10.1109/TC.2012.18 |
| [16] | Hsu, GH; Chiang, CF; Shih, LM; Hsu, LH; Tan, JJM, Conditional diagnosability of hypercubes under the comparison diagnosis model, J Syst Architect, 55, 2, 140-146 (2009) · doi:10.1016/j.sysarc.2008.10.005 |
| [17] | Hsu, GH; Tan, JJM, Conditional diagnosability of the BC networks under the comparison diagnosis model, Int Comput Symp, 1, 269-274 (2008) |
| [18] | Hung, C-N; Hsu, H-C; Liang, K-Y; Hsu, L-H, Ring embedding in faulty pancake graphs, Inf Process Lett, 86, 5, 271-275 (2003) · Zbl 1162.68496 · doi:10.1016/S0020-0190(02)00510-0 |
| [19] | Kaneko, K.; Suzuki, Y., Node-to-set disjoint paths problem in pancake graphs, IEICE Trans Inf Syst, 86, 9, 1628-1633 (2003) |
| [20] | Konstantinova, E., On Some Structural Properties of Star and Pancake Graphs, 472-487 (2013), Berlin Heidelberg: Springer, Berlin Heidelberg · Zbl 1377.05159 |
| [21] | Konstantinova, E.; Medvedev, A., Small cycles in the Pancake graph, ARS MATHEMATICA CONTEMPORANEA, 7, 1, 237-246 (2014) · Zbl 1301.05126 · doi:10.26493/1855-3974.214.0e8 |
| [22] | Lai, PL; Tan, JJM; Chang, CP; Hsu, LH, Conditional diagnosability measures for large multiprocessor systems, IEEE Trans Comput, 54, 2, 165-175 (2005) · doi:10.1109/TC.2005.19 |
| [23] | Lai, PL; Tan, JJM; Tsai, CH; Hsu, LH, The diagnosability of the matching composition network under the comparison diagnosis model, IEEE Trans Comput, 53, 8, 1064-1069 (2004) · doi:10.1109/TC.2004.50 |
| [24] | Lee, CW; Hsieh, SY, Diagnosability of two-matching composition networks under the MM model, IEEE Trans Dependable Secure Comput, 8, 2, 246-255 (2011) · doi:10.1109/TDSC.2009.52 |
| [25] | Lee, CW; Hsieh, SY, Determining the diagnosability of \((1,2)\)-matching composition networks and its applications, IEEE Trans Dependable Secure Comput, 8, 3, 353-362 (2011) · doi:10.1109/TDSC.2010.22 |
| [26] | Lin, CK; Kung, TL; Tan, JJM, Conditional-fault diagnosability of multiprocessor systems with an efficient local diagnosis algorithm under the PMC model, IEEE Trans Parallel Distrib Syst, 22, 10, 1669-1680 (2011) · doi:10.1109/TPDS.2011.46 |
| [27] | Lin, CK; Tan, JJM; Hsu, LH; Cheng, E.; Lipták, L., Conditional diagnosability of Cayley graphs generated by transposition trees, J Interconnect Netw, 9, 1-2, 83-97 (2008) · doi:10.1142/S0219265908002175 |
| [28] | Maeng J, Malek M (1981) “A comparison connection assignment for self-diagnosis of multiprocessors systems,” In: Proceedings of the 11th International Symposium on Fault-Tolerant Computing, pp 173-175 |
| [29] | Malek M (1980) “A comparison connection assignment for diagnosis of multiprocessors systems,” In: Proceedings of the 7th International Symposium on Computer Architecture, pp 31-36 |
| [30] | Nguyen, QT; Bettayeb, S., On the genus of pancake network, Int Arab J Inf Technol, 8, 3, 289-292 (2011) |
| [31] | Preparata, FP; Metze, G.; Chien, RT, On the connection assignment problem of diagnosis systems, IEEE Trans Electron Comput, 16, 12, 848-854 (1967) · Zbl 0189.16904 · doi:10.1109/PGEC.1967.264748 |
| [32] | Suzuki, Y.; Kaneko, K., An algorithm for node-disjoint paths in pancake graphs, IEICE Trans Inf Syst, E86-D, 3, 610-615 (2003) |
| [33] | Wang, D., Diagnosability of hypercubes and enhanced hypercubes under the comparison diagnosis model, IEEE Trans Comput, 48, 12, 1369-1374 (1999) · Zbl 1392.68061 · doi:10.1109/12.817401 |
| [34] | Xu, M.; Thulasiraman, K.; Hu, XD, Conditional diagnosability of matching composition networks under the PMC model, IEEE Trans Circuits Syst II, 56, 11, 875-879 (2009) · doi:10.1109/TCSII.2009.2030361 |
| [35] | Zheng, J.; Latifi, S.; Regentova, E.; Luo, K.; Wu, X., Diagnosability of star graphs under the comparison diagnosis model, Inf Process Lett, 93, 1, 29-36 (2005) · Zbl 1173.68615 · doi:10.1016/j.ipl.2004.09.011 |
| [36] | Zhou S (2009) “The conditional diagnosability of Möbius cubes under the comparison model,” In: Proceedings of the 2009 IEEE International Conference on Information and Automation, pp 96-100 |
| [37] | Zhou S (2009) “The conditional diagnosability of locally twisted cubes,” In: Proceedings of 2009 4th International Conference on Computer Science and Education, pp 221-226 |
| [38] | Zhou S (2009) “The conditional diagnosability of twisted cubes under the comparison model,” In: 2009 IEEE International Symposium on Parallel and Distributed Processing with Applications, pp 696-701 |
| [39] | Zhou, S., The conditional fault diagnosability of \((n, k)\)-star graphs, Appl Math Comput, 218, 19, 9742-9749 (2012) · Zbl 1245.05122 |
| [40] | Zhou, S.; Xu, L., Conditional fault diagnosability of pancake graphs, J Converg Inf Technol, 8, 10, 668-675 (2013) |
| [41] | Zhu, Q., On conditional diagnosability and reliability of the BC networks, J Supercomput, 45, 2, 173-184 (2008) · doi:10.1007/s11227-007-0167-8 |
| [42] | Zhu, Q.; Liu, SY; Xu, M., On conditional diagnosability of the folded hypercubes, Inf Sci, 178, 4, 1069-1077 (2008) · Zbl 1134.68014 · doi:10.1016/j.ins.2007.09.005 |
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.
