The Extra Connectivity, Extra Conditional Diagnosability, and Arrangement Graphs

The Extra Connectivity, Extra Conditional Diagnosability, and   -Diagnosability of Arrangement Graphs

Abstract

Extra connectivity is an important indicator of the robustness of a multiprocessor system in presence of failing processors. The  -extra conditional diagnosability and the  -diagnosability are two important diagnostic strategies at system-level that can significantly enhance the system’s self-diagnosing capability. The  -extra conditional diagnosability is defined under the assumption that every component of the system removing a set of faulty vertices has more than  vertices. The  -diagnosis strategy can detect up to  faulty processors which might include at most  misdiagnosed processors, where is typically a small integer number. In this paper, we analyze the combinatorial properties and fault tolerant ability for an  -arrangement graph, denoted by  , a well-known interconnection network proposed for multiprocessor systems. We first establish that the  ’s one-extra connectivityis  (  ,  ), two-extra connectivity is  ( ,  ), and three-extra connectivity is  (  ,  or ,  ), respectively. And then, we address the  -extra conditional diagnosability of under the PMC model for – formula>  . Finally, we determine that the  -arrangementgraph  is  -diagnosable (  ,  ), -diagnosable (  ,  ), and  -diagnosable (  ,  ) under the PMC model, respectively.

Comments are closed.