Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
The g-good-neighbor conditional diagnosability of star graphs under the PMC and MM* model
Li D., Lu M. Theoretical Computer Science674 (C):53-59,2017.Type:Article
Date Reviewed: Aug 7 2017

A network of processors is said to be diagnosable if its faulty nodes can be reliably identified. Identification of a faulty node depends on it having nonfaulty neighbors. The requirement that each fault-free node in a network should have at least g neighbors that are also fault-free in order to ensure that the network as a whole is diagnosable is called g-good-neighbor conditional diagnosability.

This paper builds on g-good-neighbor conditional diagnosability to develop a metric, tg, which defines the maximum number of faulty nodes that a network can sustain while ensuring that every fault-free node has at least g fault-free neighbors.

The paper considers two different models of diagnosis, the PMC model, which considers pairs of nodes that are directly connected by an edge, and the MM* model, which considers pairs of nodes that are both connected by (different) edges to a third node. Each model gives rise to a test scheme.

With the PMC model, a test scheme consists of edges (u, v) in the network, where tests are performed by node u on node v. If u is faulty, the test is unreliable, and if u is fault-free, the test reliably determines whether or not v is faulty.

With the MM* model, a test scheme consists of pairs of edges, (u, w) and (v, w) where each pair of edges has the node w in common. If w is faulty, the test is unreliable. Otherwise, it reliably determines whether or not v and w are faulty.

In either case, a test result, called a syndrome, combines all the test results for a test scheme in a single result. A subset of the nodes in a network is consistent with a syndrome if the syndrome is produced when all the nodes in the set are faulty and all the other nodes are fault-free. Two distinct sets of faulty nodes are said to be distinguishable if the syndromes with which they are consistent are disjoint. Otherwise, they are indistinguishable.

A g-good-neighbor conditional faulty set is a set of faulty nodes that nonetheless leaves every nonfaulty node with at least g good neighbors. A system G is g-good-neighbor conditionally t-diagnosable if every disjoint pair of node subsets, F1 and F2, of cardinality at most t, is distinguishable.

They key result of the paper is that for a star network Sn, with n! nodes and (n – 1) n!/2 edges, the g-good-neighbor conditional diagnosability of Sn is 0 < = g < = n – 2 and n > = 4, tg (Sn) = (ng)( g + 1)! – 1.

The paper is readable and well presented, despite some unconventional uses of English. The results are likely to be useful to anyone with an interest in the diagnosis of faults in networked systems.

The paper also provides a useful starting point for bridging the gap between diagnosis based on symbolic reasoning and failure mode effects analysis and diagnosis based on properties of graphs.

Reviewer:  Edel Sherratt Review #: CR145461 (1710-0662)
Bookmark and Share
 
Network Architecture And Design (C.2.1 )
 
 
Diagnostics (B.4.5 ... )
 
 
Reliability, Testing, And Fault-Tolerance (B.4.5 )
 
 
Performance of Systems (C.4 )
 
Would you recommend this review?
yes
no
Other reviews under "Network Architecture And Design": Date
Designing data networks
Ellis R., Prentice-Hall, Inc., Upper Saddle River, NJ, 1986. Type: Book (9789780132018647)
Apr 1 1986
Internetworking
Pouzin L., Prentice-Hall, Inc., Upper Saddle River, NJ, 1986. Type: Book (9789780131650503)
Feb 1 1987
Broadband network technology: an overview for the data and telecommunications industries
Cooper E., Prentice-Hall, Inc., Upper Saddle River, NJ, 1986. Type: Book (9789780130833792)
Oct 1 1987
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy