On g-extra conditional diagnosability of hypercubes and folded hypercubes

摘要

Diagnosability of a multiprocessor system is one important study topic, which plays an important role in measuring of the reliability of multiprocessor systems. In the work of Zhang et al. in 2016, they proposed a new measure for fault diagnosis of systems, namely, g-extra conditional diagnosability. It is defined as the diagnosability of a multiprocessor system under the assumption that every fault-free component contains more than g vertices, which can measure the reliability of interconnection networks in heterogeneous environments more accurately than traditional diagnosability. As two kind of favorable topology structures of interconnection networks, the n-dimensional hypercubes Q(n) and folded hypercubes FQ(n) have many good properties. In this paper, we investigate their g-extra conditional diagnosability and show that (a) the g-extra conditional diagnosability of Q(n) is (g + 1)n - g - C-g(2) for n = 5 and 1 = g = n-1/4 under the MM* model; (b) the g -extra conditional diagnosability of FQ(n) is (g + 1)n - 1 for n = 9 and 1 = g = n/4 under the MM* model. (C) 2017 Elsevier B.V. All rights reserved.