Diagnosability of star graphs with missing edges
type: Item
instance of: scholarly article
title: Diagnosability of star graphs with missing edges
zbMATH Open document ID: 1257.68042
author: Chieh-Feng Chiang
author: Guo-Huang Hsu
author: Lun-Min Shih
author: Jimmy J. M. Tan
published in: Information Sciences
publication date: 2012-10-02T00:00:00Z
reviewed by: Zhizhang Shen
Mathematics Subject Classification ID: 68M15
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68M14
zbMATH DE Number: 6089563
zbMATH Keywords: star graph
zbMATH Keywords: comparison diagnosis model
zbMATH Keywords: \(\text{MM}^{\ast }\) diagnosis model
zbMATH Keywords: local diagnosability
zbMATH Keywords: extended star structure
zbMATH Keywords: strong local diagnosability property
MaRDI profile type: Publication
full work available at URL: j.ins.2011.11.012
OpenAlex ID: W2149530815
cites work: Linearly many faults in Cayley graphs generated by transposition trees
cites work: Using Node Diagnosability to Determine t-Diagnosability under the Comparison Diagnosis Model
cites work: Strongly Diagnosable Systems under the Comparison Diagnosis Model
cites work: Strongly Diagnosable Product Networks Under the Comparison Diagnosis Model
cites work: On the fault-diameter of the star graph
cites work: Robustness of star graph network under link failure
cites work: Hyper Hamiltonian laceability on edge fault star graph
cites work: On self-diagnosable multiprocessor systems: diagnosis by the comparison approach
cites work: Improving bounds on link failure tolerance of the star graph
cites work: Diagnosability of star graphs under the comparison diagnosis model
DOI: 10.1016/J.INS.2011.11.012
review text: Thanks to constant technological progress, multiprocessor systems with ever increasing number of interconnected computing nodes are becoming a reality. To address their reliability, it is ideal, and technically feasible, to have a self-diagnosable system where the computing nodes are able to detect faulty ones by themselves. One major approach to this regard is called the comparison model [\textit{M. Malek}, ``A comparison connection assignment for diagnosis of multiprocessors systems'', in: Proceedings of the 7th international symposium on computer architecture. 31--35 (1980); \textit{J. Maeng} and \textit{M. Malek}, ``A comparison connection assignment for self-diagnosis of multiprocessors systems'', in: Proceedings of the 11th international symposium on fault tolerant computing. 173--175 (1981)], where each node, as a comparator, performs a diagnosis by sending the same input to every pair of its distinct neighbors, comparing their responses, and then deciding the faulty status of their neighbors, when the comparator itself is not faulty. A system level diagnosis is reached based on such node level diagnoses. The number of detectable faulty nodes in such a multiprocessor system certainly depends on the topology of its interconnection network, as well as the modeling assumptions, and the maximum number of necessarily detectable faulty nodes in such a network is called its diagnosability.NEWLINENEWLINESeveral attempts have been made to provide a realistic and practical characterization of this measurement of diagnosability. For example, `conditional diagnosability' assumes that no faulty set contains all the neighbors of any node, based on the observation that there would be no way to decide the faulty status of a node, if all its neighboring comparators are faulty simultaneously, a statistically unlikely, if not impossible, phenomenon. Conditional diagnosability of various networks have been decided, based on a central result that relates the conditional diagnosab…
description: scientific article; zbMATH DE number 6089563