Two-round diagnosability measures for multiprocessor systems

DOI10.1155/2020/9535818MaRDI QIDQ781778zbMATH OpenOpenAlexFDO

Authors Jiarong Liang, Qian Zhang, Changzhen Li

Publication date 18 July 2020

Published in Complexity (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1155/2020/9535818

Mathematics Subject Classification ID

Mathematical problems of computer architecture (68M07) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Review text

Summary: In a multiprocessor system, as a key measure index for evaluating its reliability, diagnosability has attracted lots of attentions. Traditional diagnosability and conditional diagnosability have already been widely discussed. However, the existing diagnosability measures are not sufficiently comprehensive to address a large number of faulty nodes in a system. This article introduces a novel concept of diagnosability, called two-round diagnosability, which means that all faulty nodes can be identified by at most a one-round replacement (repairing the faulty nodes). The characterization of two-round \(t\)-diagnosable systems is provided; moreover, several important properties are also presented. Based on the abovementioned theories, for the \(n\)-dimensional hypercube \(\left( Q_n\right)\), we show that its two-round diagnosability is \(\left( n^2 + n / 2\right)\), which is \(\left( n + 1 / 2\right)\) times its classic diagnosability. Furthermore, a fault diagnosis algorithm is proposed to identify each node in the system under the PMC model. For \(Q_n\), we prove that the proposed algorithm is the time complexity of \(O\left( n 2^n\right)\).

Recommendations

• Conditional diagnosability of balanced hypercubes under the PMC model
• On diagnosability of large multiprocessor networks
• On diagnosability of large multiprocessor networks
• Fault diagnosability of DQcube under the PMC model
• Conditional fault diagnosability of dual-cubes

Cites work

• A Fast Pessimistic Diagnosis Algorithm for Hypercube-Like Networks under the Comparison Model
• A fast pessimistic one-step diagnosis algorithm for hypercube multicomputer systems
• A kind of conditional fault tolerance of (n, k)-star graphs
• Component connectivity of the hypercubes
• Conditional diagnosability of multiprocessor systems based on complete-transposition graphs
• Diagnosability of star graphs under the comparison diagnosis model
• Edge-pancyclicity and path-embeddability of bijective connection graphs
• Efficient unicast in bijective connection networks with the restricted faulty node set
• On conditional fault tolerance and diagnosability of hierarchical cubic networks
• On the t/k-diagnosability of BC networks
• On the maximal connected component of a hypercube with faulty vertices III
• Online policy iterative-based \(H_\infty\) optimization algorithm for a class of nonlinear systems
• Optimization of Reduced Dependencies for Synchronous Sequential Machines
• The t/k-Diagnosability of Star Graph Networks
• The spined cube: a new hypercube variant with smaller diameter
• The strong local diagnosability of a hypercube network with missing edges

Cited in

(3)

• Partial and complete local diagnosis in computer systems with circulant structure
• Fault diagnosability of DQcube under the PMC model
• Necessary and sufficient conditions for t-diagnosability of multiprocessor computer systems for various models of nonreliable testing established using the system graph-theoretical model

This page was built for publication: Two-round diagnosability measures for multiprocessor systems

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