g-Good-Neighbor Diagnosability of Arrangement Graphs under the PMC Model and MM* Model - Shiying Wang; Yunxia Ren (Information, 2018)
Diagnosability of a multiprocessor system is an important research topic. The system and interconnection network has a underlying topology, which usually presented by a graph <semantics> G = ( V , E ) </semantics> . In 2012, a measurement for fault tolerance of the graph was proposed by Peng et al. This measurement is called the g-good-neighbor diagnosability that restrains every fault-free node to contain at least g fault-free neighbors. Under the PMC model, to diagnose the system, two adjacent nodes in G are can perform tests on each other. Under the MM model, to diagnose the system, a node sends the same task to two of its neighbors, and then compares their responses. The MM* is a special case of the MM model and each node must test its any pair of adjacent nodes of the system. As a famous topology structure, the <semantics> ( n , k ) </semantics> -arrangement graph <semantics> A n , k </semantics> , has many good properties. In this paper, we give the g-good-neighbor diagnosability of <semantics> A n , k </semantics> under the PMC model and MM* model.