Local Fault Diagnosis Analysis Based on Block Pattern of Regular Diagnosable Networks

Fault diagnosability can reflect the actual self diagnosing capability of a multiprocessor system better. However, people usually focus on the overall information and neglect the important local information. In order to reflect the locality of a system at a node better, this paper proposes a novel fault diagnosis strategy, called x-block local fault diagnosability (x-BLFD), where the x-block condition requires more than x connected fault-free nodes. Then, we characterize some important properties about the x-BLFD of multiprocessors interconnected networks under the Preparata/Metze/Chien model (P/M/C), and further propose the x-BLFD in an <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$f(x)$ </tex-math></inline-formula>-extended block network with the minimum <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(x+1)$ </tex-math></inline-formula>-subnetwork degree at some node. We also establish an approximate algorithm to calculate the x-BLFD of a large-scale diagnosable network at some node, and analyze the experimental performance of large-scale networks. Furthermore, we apply our proposed conclusion to obtain the x-BLFD of 16 well-known networks at some node directly under P/M/C, including dual cubes, hierarchical cubic networks, DQcubes, twisted hypercubes, Bicube networks, crossed cubes, folded hypercubes, k-ary n-cubes, balanced hypercubes, BC graphs, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(n,k)$ </tex-math></inline-formula>-star graphs, Cayley graphs generated by transposition trees, bubble-sort star graphs, split-star networks, data center networks, and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(n,k)$ </tex-math></inline-formula>-arrangement graphs. Finally, we compare the x-BLFD with the diagnosability, conditional diagnosability, pessimistic diagnosability, and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$t/k$ </tex-math></inline-formula>-diagnosability by a large number of detailed numerical analysis. It can be seen that the x-BLFD is greater than all the other types of fault diagnosabilities.