Research ArticleOpen AccessGoogle Scholar indexed
Some Properties of the <i>g</i>-Good-Neighbor (<i>g</i>-Extra) Diagnosability of a Multiprocessor System
School of Mathematics and Information Science, Henan Normal University, Xinxiang, China
School of Mathematics and Information Science, Henan Normal University, Xinxiang, China
- 1 School of Mathematics and Information Science, Henan Normal University, Xinxiang, China
- 2 School of Mathematics and Information Science, Henan Normal University, Xinxiang, China
American Journal of Computational Mathematics·Volume 06 (2016)·Pages 259–266·Published 4 July 2016·DOI10.4236/ajcm.2016.63027
Copy link · social · email
Abstract
Diagnosability of a multiprocessor system is one important study topic. In 2012, Peng <i>et al. </i> proposed a measure for fault tolerance of the system, which is called the <i>g</i>-good-neighbor diagnosability that restrains every fault-free node containing at least <i>g</i> fault-free neighbors. In 2015, Zhang <i>et al. </i> proposed a measure for fault diagnosis of the system, namely, <i>g</i>-extra diagnosability, which restrains that every fault-free component has at least <i>g</i>+1 fault-free nodes. In this paper, we obtain some properties of the <i>g</i>-good-neighbor (<i>g</i>-extra) diagnosability of the system and give the <i>g</i>-good-neighbor (<i>g</i>-extra) diagnosability of some graphs under the PMC model and MM<sup>*</sup> model.
KeywordsInterconnection NetworkCombinatoricsDiagnosability
- Dahbura, A.T. and Masson, G.M. (1984) An Fault Identification Algorithm for Diagnosable Systems. IEEE Transactions on Computers, 33, 486-492. http://dx.doi.org/10.1109/TC.1984.1676472
- Fan, J. (2002) Diagnosability of Crossed Cubes under the Comparison Diagnosis Model. IEEE Transactions on Parallel and Distributed Systems, 13, 1099-1104. http://dx.doi.org/10.1109/TPDS.2002.1041887
- Lai, P.-L., Tan, J..J.M., Chang, C.-P. and Hsu, L.-H. (2005) Conditional Diagnosability Measures for Large Multiprocessor Systems. IEEE Transactions on Computers, 54, 165-175. http://dx.doi.org/10.1109/TC.2005.19
- Preparata, F.P., Metze, G. and Chien, R.T. (1967) On the Connection Assignment Problem of Diagnosable Systems. IEEE Transactions on Computers, EC-16, 848-854. http://dx.doi.org/10.1109/PGEC.1967.264748
- Maeng, J. and Malek, M. (1981) A Comparison Connection Assignment for Self-Diagnosis of Multiprocessor Systems. Proceeding of 11th International Symposium on Fault-Tolerant Computing, Portland, 24-26 June 1981, 173-175.
- Peng, S.-L., Lin, C.-K., Tan, J.J.M. and Hsu, L.-H. (2012) The g-Good-Neighbor Conditional Diagnosability of Hypercube under PMC Model. Applied Mathematics and Computation, 218, 10406-10412. http://dx.doi.org/10.1016/j.amc.2012.03.092
- Wang, S. and Han, W. (2016) The g-Good-Neighbor Conditional Diagnosability of n-Dimensional Hypercubes under the MM* Model. Information Processing Letters, 116, 574--577. http://dx.doi.org/10.1016/j.ipl.2016.04.005
- Yuan, J., Liu, A., Ma, X., Liu, X., Qin, X. and Zhang, J. (2015) The g-Good-Neighbor Conditional Diagnosability of k-Ary n-Cubes under the PMC Model and MM* Model. IEEE Transactions on Parallel and Distributed Systems, 26, 1165-1177. http://dx.doi.org/10.1109/TPDS.2014.2318305
- Yuan, J., Liu, A., Qin, X., Zhang, J. and Li, J. (2016) g-Good-Neighbor Conditional Diagnosability Measures for 3-Ary n-Cube Networks. Theoretical Computer Science, 622, 144-162. http://dx.doi.org/10.1016/j.tcs.2016.01.046
- Wang, M., Guo, Y. and Wang, S. (2015) The 1-Good-Neighbor Diagnosability of Cayley Graphs Generated by Transposition Trees under the PMC Model and MM* Model. International Journal of Computer Mathematics, 1-12. http://dx.doi.org/10.1080/00207160.2015.1119817
- Wang, M., Lin, Y. and Wang, S. (2016) The 2-Good-Neighbor Diagnosability of Cayley Graphs Generated by Transposition Trees under the PMC Model and MM* Model. Theoretical Computer Science, 628, 92-100. http://dx.doi.org/10.1016/j.tcs.2016.03.019