Diagnosable evaluation of DCC linear congruential graphs under the PMC diagnostic model. (English) Zbl 1176.68034
Summary: A DCC (disjoint consecutive cycles) linear congruential graph \(G(F,n)\) consists of \(n\) nodes and is generated by a set of linear functions \(F\) with special properties. It was proved that \(G(F,n)\) is a \(2t\)-regular graph and has connectivity \(2t\), where \(t=|F|\) and \(1\leqslant t\leqslant p-1 (n=2^p\) for some integer \(p)\). For a multiprocessor system, its diagnosability is critical to measure the performance. In this paper, we study the diagnosability of \(G(F,2^p)\) under the precise and pessimistic diagnosis strategies based on the PMC (Preparata, Metze, and Chien) diagnostic model. It is proved that \(G(F,2^p)\) is \(2t\)-diagnosable and \((4t-5)/(4t-5)\)-diagnosable under the two diagnosis strategies, respectively, where \(p\geqslant 3\) and \(2\leqslant t\leqslant p-1\). In addition, the diagnosability of DCC linear congruential graphs is compared with that of BC (bijective connection) graphs.
MSC:
| 68M15 | Reliability, testing and fault tolerance of networks and computer systems |
Keywords:
multiprocessor system; DCC linear congruential graph; diagnosability; precise diagnosis strategy; pessimistic diagnosis strategy; PMC diagnostic modelReferences:
| [1] | Ahlswede, R.; Aydinian, H., On diagnosability of large multiprocessor networks, Discrete Applied Mathematics, 156, 18, 3464-3474 (2008) · Zbl 1168.68007 |
| [2] | Araki, T.; Shibata, Y., \((t,k)\)-Diagnosable system: a generalization of the PMC models, IEEE Transactions on Computers, 52, 7, 971-975 (2003) |
| [3] | Armstrong, J. R.; Gray, F. G., Fault diagnosis in a boolean \(n\)-cube array of multiprocessors, IEEE Transactions on Computers, 30, 8, 587-590 (1981) · Zbl 0461.94023 |
| [4] | Chang, G.-Y.; Chen, G.-H.; Chang, G. J., \((t,k)\)-Diagnosis for matching composition networks, IEEE Transactions on Computers, 55, 1, 88-92 (2006) |
| [5] | Chwa, K. Y.; Hakimi, S. L., On fault identification in diagnosable systems, IEEE Transactions on Computers, 30, 6, 414-422 (1981) · Zbl 0456.94032 |
| [6] | Dahbura, A. T.; Sabnani, K. K.; King, L. L., The comparison approach to multiprocessor fault diagnosis, IEEE Transactions on Computers, 36, 3, 373-378 (1987) |
| [7] | Fan, J., Diagnosability of the Möbius cubes, IEEE Transactions on Parallel and Distributed Systems, 9, 9, 923-928 (1998) |
| [8] | Fan, J.; He, L., BC interconnection networks and their properties, Chinese Journal of Computers, 26, 1, 84-90 (2003) |
| [9] | Fan, J.; Jia, X., Edge-pancyclicity and path-embeddability of bijective connection graphs, Information Sciences, 178, 340-351 (2008) · Zbl 1128.68075 |
| [10] | Fan, J.; Lin, X., The \(t/k\)-diagnosability of the BC Graphs, IEEE Transactions on Computers, 54, 2, 176-184 (2005) |
| [11] | A.D. Friedman, A new measure of digital system diagnosis, in: Proceeding of the Fifth International, Symposium on Fault-Tolerant Computing, 1975, pp. 167-170.; A.D. Friedman, A new measure of digital system diagnosis, in: Proceeding of the Fifth International, Symposium on Fault-Tolerant Computing, 1975, pp. 167-170. |
| [12] | Hakimi, S. L.; Amin, A. T., Characterization of the connection assignment of diagnosable systems, IEEE Transactions on Computers, 23, 1, 86-88 (1974) · Zbl 0278.94018 |
| [13] | Hakimi, S. L.; Nakajima, K., An adaptive system diagnosis, IEEE Transactions on Computers, 33, 3, 234-240 (1984) · Zbl 0528.94031 |
| [14] | Hakimi, S. L.; Schmeichel, E. F., An adaptive algorithm for system level diagnosis, Journal of Algorithms, 5, 526-530 (1984) · Zbl 0555.94020 |
| [15] | Hsu, G.-H.; Tan, J. J.M., A local diagnosability measure for multiprocessor systems, IEEE Transactions on Parallel and Distributed Systems, 18, 5, 598-607 (2007) |
| [16] | Kavianpour, A.; Kim, K. H., Diagnosability of hypercubes under the pessimistic one-step diagnosis strategy, IEEE Transactions on Computers, 40, 2, 232-237 (1991) |
| [17] | Opatrny, J.; Sottean, D.; Srinivasan, N.; Thulasiraman, K., DCC linear congruential graphs: a new class of interconnection networks, IEEE Transactions on Computers, 45, 2, 156-164 (1996) · Zbl 1068.68559 |
| [18] | Preparata, F. P.; Metze, G.; Chien, R. T., On the connection assignment problem of diagnosable systems, IEEE Transactions on Electronic Computers, 16, 12, 848-854 (1967) · Zbl 0189.16904 |
| [19] | Somani, A. K.; Agarwal, V. K.; Avis, D., A generalized theory for system-level diagnosis, IEEE Transactions on Computers, 36, 5, 538-546 (1987) · Zbl 0612.94020 |
| [20] | Somani, A. K.; Agarwal, V. K., Distributed diagnosis algorithms for regular interconnection networks, IEEE Transactions on Computers, 41, 7, 899-906 (1992) · Zbl 1395.68064 |
| [21] | Somani, A. K.; Peleg, O., On diagnosability of large fault sets in regular topology-based computer systems, IEEE Transactions on Computers, 45, 8, 892-903 (1996) · Zbl 1057.68535 |
| [22] | Wang, D., Diagnosability of enhanced hypercubes, IEEE Transactions on Computers, 43, 9, 1054-1061 (1994) · Zbl 1061.68507 |
| [23] | Yang, C. L.; Marson, G. M.; Leonetti, R., On fault identification and isolation in \(t1/t1\)-diagnosable systems, IEEE Transactions on Computers, 35, 7, 639-644 (1986) · Zbl 0588.94018 |
| [24] | Zheng, S.; Zhou, S., Diagnosability of the incomplete star graphs, Tsinghua Science and Technology, 12, 1, 105-109 (2007) · Zbl 1174.68472 |
| [25] | Zhu, Q.; Liu, S.-Y.; Xu, M., On conditional diagnosability of the folded hypercubes, Information Sciences, 178, 4, 1069-1077 (2008) · Zbl 1134.68014 |
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.
