IEEE Transactions on Parallel and Distributed Systems · 2014 · 103 citations · 42 references
EngineeringComputer EngineeringComputer ScienceFault ToleranceFault-tolerant ComputingFault-tolerant SystemsGraph TheoryHardware Fault ToleranceReliable System DesignConditional DiagnosabilityDiagnosabilityExtra ConnectivityFault Tolerance In MultiprocessorsGraph ConnectivityGraph Connectivity AnalysisNode Connectivity
Extra connectivity, diagnosability, and conditional diagnosability are all important measures for a multiprocessor system's ability to diagnose and tolerate faults. In this paper, we analyze the fault tolerance ability for the alternating group graph, a well-known interconnection network proposed for multiprocessor systems, establish the h-extra connectivity, where 1 ≤ h ≤ 3, and prove that the conditional diagnosability of an n-dimensional alternating group graph, denoted by AG <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sub> , is 8n - 27 (n ≥ 4) under the PMC model. This is about four times of the AG <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sub> 's traditional diagnosability. As a byproduct, the strong diagnosability of AG <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sub> is also obtained.
42
On the extraconnectivity of graphs
J. Fàbrega, M.A. Fiol · Discrete Mathematics · 1996 · 401 citations
Conditional diagnosability measures for large multiprocessor systems
Pao-Lien Lai, J. Tan, Chien-Ping Chang et al. · IEEE Transactions on Computers · 2005 · 400 citations