Fault diagnosability of arrangement graphs

DOI10.1016/J.INS.2013.04.038zbMATH Open1337.68215arXiv1204.4018OpenAlexW2115228197MaRDI QIDQ497286FDOQ497286

Authors: Shuming Zhou, Jun-Ming Xu 

Publication date: 23 September 2015

Published in: Information Sciences (Search for Journal in Brave)

Abstract: The growing size of the multiprocessor system increases its vulnerability to component failures. It is crucial to locate and to replace the faulty processors to maintain a system's high reliability. The fault diagnosis is the process of identifying faulty processors in a system through testing. This paper shows that the largest connected component of the survival graph contains almost all remaining vertices in the $(n,k)$-arrangement graph $A_{n,k}$ when the number of moved faulty vertices is up to twice or three times the traditional connectivity. Based on this fault resiliency, we establishes that the conditional diagnosability of $A_{n,k}$ under the comparison model. We prove that for $kgeq4$, $ngeqk+2$, the conditional diagnosability of $A_{n,k}$ is $(3k-2)(n-k)-3$; the conditional diagnosability of $A_{n,n-1}$ is $3n-7$ for $ngeq5$.

Full work available at URL: https://arxiv.org/abs/1204.4018

Recommendations

• Conditional diagnosability of arrangement graphs under the PMC model
• The conditional fault diagnosability of \((n, k)\)-star graphs
• Conditional fault diagnosability of dual-cubes
• The conditional diagnosability of crossed cubes under the comparison model
• Conditional fault diagnosis of hierarchical hypercubes

zbMATH Keywords

diagnosabilityfault tolerance\((ncomparison diagnosisk)\)-arrangement graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Cites Work

• Arrangement graphs: A class of generalized star graphs
• Linearly many faults in Cayley graphs generated by transposition trees
• On the arrangement graph.
• Title not available (Why is that?)
• A group-theoretic model for symmetric interconnection networks
• Title not available (Why is that?)
• Title not available (Why is that?)
• On self-diagnosable multiprocessor systems: diagnosis by the comparison approach
• Title not available (Why is that?)
• Optimization of Reduced Dependencies for Synchronous Sequential Machines
• Conditional diagnosability of alternating group networks
• Panpositionable hamiltonicity and panconnectivity of the arrangement graphs
• Embedding of cycles in arrangement graphs
• Linearly many faults in 2-tree-generated networks
• On the maximal connected component of a hypercube with faulty vertices III
• On the maximal connected component of hypercube with faulty vertices (II)
• On the maximal connected component of hypercube with faulty vertices
• Increasing the connectivity of the star graphs
• On Fault Identification in Diagnosable Systems
• Diagnosable evaluation of DCC linear congruential graphs under the PMC diagnostic model
• On super and restricted connectivity of some interconnection networks.
• On conditional diagnosability of the folded hypercubes
• Fault-Tolerant Broadcasting on the Arrangement Graph
• Fault resiliency of Cayley graphs generated by transpositions
• Generalized matching networks and their properties
• Largest connected component of a star graph with faulty vertices

Cited In (24)

• The \(t/s\)-diagnosability and \(t/s\)-diagnosis algorithm of folded hypercube under the PMC/MM* model
• Relationship between conditional diagnosability and 2-extra connectivity of symmetric graphs
• The conditional fault diagnosability of \((n, k)\)-star graphs
• Fault tolerance and diagnosability of burnt pancake networks under the comparison model
• The relationship between extra connectivity and conditional diagnosability of regular graphs under the PMC model
• \(g\)-good-neighbor conditional diagnosability of star graph networks under PMC model and MM\(^*\) model
• One-to-one disjoint path covers on alternating group graphs
• Fault diagnosability of data center networks
• Relating the extra connectivity and the conditional diagnosability of regular graphs under the comparison model
• Conditional diagnosability and strong diagnosability of split-star networks under the PMC model
• The intermittent diagnosability for two families of interconnection networks under the PMC model and MM* model
• Hybrid fault diagnosis capability analysis of triangle-free graphs
• Fault identification: An approach based on propagation digraphs
• The symmetry property of (n,k)‐arrangement graph
• The pessimistic diagnosability of three kinds of graphs
• Researches for more reliable arrangement graphs in multiprocessor computer system
• Note on reliability evaluation of arrangement graphs
• Conditional diagnosability of the round matching composition networks
• Conditional diagnosability of arrangement graphs under the PMC model
• Title not available (Why is that?)
• Structure fault-tolerance of arrangement graphs
• Conditional diagnosability of multiprocessor systems based on Cayley graphs generated by transpositions
• Parallel routing in regular networks with faults
• Hybrid fault diagnosis capability analysis of hypercubes under the PMC model and \(\mathrm{MM}^\ast\) model

This page was built for publication: Fault diagnosability of arrangement graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q497286)