The Component Diagnosability of General Networks

DOI10.1142/S0129054121500374MaRDI QIDQ6114857zbMATH OpenOpenAlexFDO

Authors Hongbin Zhuang, Wenzhong Guo, Xiaoyan Li, Ximeng Liu, Cheng-Kuan Lin

Publication date 15 August 2023

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

component diagnosabilityfault diagnosisgeneral networksMM* modelPMC model

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Distributed systems (68M14) Reliability, testing and fault tolerance of networks and computer systems (68M15) Graph theory (including graph drawing) in computer science (68R10)

Abstract: The processor failures in a multiprocessor system have a negative impact on its distributed computing efficiency. Because of the rapid expansion of multiprocessor systems, the importance of fault diagnosis is becoming increasingly prominent. The $h$-component diagnosability of $G$, denoted by $c{t}_h(G)$, is the maximum number of nodes of the faulty set $F$ that is correctly identified in a system, and the number of components in $G-F$ is at least $h$. In this paper, we determine the $(h+1)$-component diagnosability of general networks under the PMC model and MM${}^{\ast }$ model. As applications, the component diagnosability is explored for some well-known networks, including complete cubic networks, hierarchical cubic networks, generalized exchanged hypercubes, dual-cube-like networks, hierarchical hypercubes, Cayley graphs generated by transposition trees (except star graphs), and DQcube as well. Furthermore, we provide some comparison results between the component diagnosability and other fault diagnosabilities.

Recommendations

• Conditional diagnosability of component-composition graphs under the PMC model
• The component connectivity, component diagnosability, and \(t/k\)-diagnosability of bicube networks
• Diagnosability for two families of composition networks
• On diagnosability of large multiprocessor networks
• Conditional fault diagnosability of dual-cubes

Cites work

• A strong connectivity property of the generalized exchanged hypercube
• An 0(n^2.5) Fault Identification Algorithm for Diagnosable Systems
• Component connectivity of the hypercubes
• Conditional connectivity of Cayley graphs generated by transposition trees
• Diagnosability of Cayley graphs generated by transposition trees with missing edges
• DVcube: a novel compound architecture of disc-ring graph and hypercube-like graph
• Equal relation between g-good-neighbor diagnosability under the PMC model and g-good-neighbor diagnosability under the MM^ model of a graph
• Fault diagnosability of DQcube under the PMC model
• Graph theory
• KCube: a novel architecture for interconnection networks
• Linearly many faults in Cayley graphs generated by transposition trees
• Linearly many faults in dual-cube-like networks
• On component connectivity of hierarchical star networks
• On self-diagnosable multiprocessor systems: diagnosis by the comparison approach
• Optimization of Reduced Dependencies for Synchronous Sequential Machines
• Relation of extra edge connectivity and component edge connectivity for regular networks
• Relationship between conditional diagnosability and 2-extra connectivity of symmetric graphs
• Relationship between extra edge connectivity and component edge connectivity for regular graphs
• Reliability analysis of data center networks based on precise and imprecise diagnosis strategies
• Structural properties of generalized exchanged hypercubes
• The g-extra conditional diagnosability and sequential t/k-diagnosability of hypercubes
• The \(g\)-good-neighbor conditional diagnosability of hypercube under PMC model
• The extra connectivity, extra conditional diagnosability and \(t/k\)-diagnosability of the data center network DCell

Cited in

(17)

• Number of mutual connections in neighborhoods and its application to self-diagnosable systems
• The \(R_g\)-conditional diagnosability of international networks
• Characterization of component diagnosability of regular networks
• The upper and lower bounds of \(R_g\)-conditional diagnosability of networks
• Diagnosability for two families of composition networks
• The component connectivity, component diagnosability, and \(t/k\)-diagnosability of bicube networks
• r-component diagnosability of hypercubes under the PMC model
• Extra (component) connectivity and diagnosability of bubble sort networks
• scientific article; zbMATH DE number 6718623 (Why is no real title available?)
• The -Diagnosability for Regular Networks
• Computing the (t,k)-diagnosability of component-composition graphs and its application
• Diagnosability of Two-Matching Composition Networks
• scientific article; zbMATH DE number 7144825 (Why is no real title available?)
• Relating g-good-neighbor connectivity and g-good-neighbor diagnosability of strong digraph network
• An efficient two-stage diagnostic algorithm for assessing system reliability
• The h-component diagnosability of alternating group graphs
• A general technique to establish the asymptotic conditional diagnosability of interconnection networks

This page was built for publication: The Component Diagnosability of General Networks

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