Back
 AJCM  Vol.6 No.3 , September 2016
Some Properties of the g-Good-Neighbor (g-Extra) Diagnosability of a Multiprocessor System
Abstract: Diagnosability of a multiprocessor system is one important study topic. In 2012, Peng et al. proposed a measure for fault tolerance of the system, which is called the g-good-neighbor diagnosability that restrains every fault-free node containing at least g fault-free neighbors. In 2015, Zhang et al. proposed a measure for fault diagnosis of the system, namely, g-extra diagnosability, which restrains that every fault-free component has at least g+1 fault-free nodes. In this paper, we obtain some properties of the g-good-neighbor (g-extra) diagnosability of the system and give the g-good-neighbor (g-extra) diagnosability of some graphs under the PMC model and MM* model.
Cite this paper: Ren, Y. and Wang, S. (2016) Some Properties of the g-Good-Neighbor (g-Extra) Diagnosability of a Multiprocessor System. American Journal of Computational Mathematics, 6, 259-266. doi: 10.4236/ajcm.2016.63027.
References

[1]   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

[2]   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

[3]   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

[4]   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

[5]   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.

[6]   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

[7]   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

[8]   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

[9]   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

[10]   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

[11]   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

[12]   Zhang, S. and Yang, W. (2016) The g-Extra Conditional Diagnosability and Sequential t/k-Diagnosability of Hypercubes. International Journal of Computer Mathematics, 93, 482-497.

[13]   Wang, S., Wang, Z. and Wang, M. (2016) The 2-Extra Connectivity and 2-Extra Diagnosability of Bubble-Sort Star Graph Networks. The Computer Journal, 1-18.
http://dx.doi.org/10.1093/comjnl/bxw037

[14]   Sengupta, A. and Dahbura, A.T. (1992) On Self-Diagnosable Multiprocessor Systems: Diagnosis by the Comparison Approach. IEEE Transactions on Computers, 41, 1386-1396.
http://dx.doi.org/10.1109/12.177309

[15]   Hsieh, S.Y. and Kao, C.Y. (2013) The Conditional Diagnosability of k-Ary n-Cubes under the Comparison Diagnosis Model. IEEE Transactions on Computers, 62, 839-843.
http://dx.doi.org/10.1109/TC.2012.18

[16]   Zhou, S., Wang, J., Xu, X. and Xu, J.-M. (2013) Conditional Fault Diagnosis of Bubble Sort Graphs under the PMC Model. Intelligence Computation and Evolutionary Computation, 180, 53-59.
http://dx.doi.org/10.1007/978-3-642-31656-2_8

[17]   Bondy, A. and Murty, U.S.R. (2007) Graph Theory. Springer, New York.

 
 
Top