Diagnosability of star graphs with missing edges (Q454954)

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. Several 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 diagnosability of a network to the existence of certain length-two paths within this network [\textit{A. Sengupta} and \textit{A. Dahbura}, ``On self-diagnosable multiprocessor systems: diagnosis by the comparison approach'', IEEE Trans. Comput. 41, 1386--1396 (1992)]. On the other hand, `local diagnosability' of a network addresses the diagnosability of individual nodes in a network. For a technical definition, readers are referred to [\textit{G.-H. Hsu} and \textit{J.M. Tan}, ``A local diagnosability measure for multiprocessor systems'', IEEE Trans. Parallel Distributed Syst. 18, No. 5, 598--607 (2007)]. Roughly speaking, as long as a faulty set contains at most \(t\) nodes, any node with its local diagnosability being \(t\) can be correctly diagnosed. This notion is also related to the diagnosability of the whole system in the sense that the diagnosability of the whole system is \(t\) if and only if the local diagnosabilities of all its nodes are at least \(t.\) Similar to the conditional diagnosability case, the existence of a basic structure also plays the central role in establishing the local diagnosability of a node in a network. This time, what we need turns out to be an extended star of order \(r\), obtained from a star \(K_{1, r}\) by replacing each edge with a length-four path. It is shown in [Hsu and Tan, loc. cit.] that, let \(v\) be a vertex of \(G,\) the local diagnosability of \(v\) is \(d_G(v),\) thus \(v\) is strongly locally diagnosable, if there exists an extended star of order \(d_G(v)\) at \(v\) in \(G,\) where \(d_G(v)\) refers to the degree of \(v\) in \(G.\) This paper shows that the above condition is satisfied for every vertex \(v\) in the often studied star network \(S_n\) [\textit{S. B. Akers} and \textit{B. Krishnamurthy}, IEEE Trans. Comput. 38, No. 4, 555--566 (1989; Zbl 0678.94026)], even when up to \(n-3\) edges are missing. It is interesting to observe that such a practical matter of multiprocessor system fault-tolerance diagnosis is reduced to a pure construction and identification effort in terms of graph theory. I expect many works to follow along this line for other networks as well.