Diagnosability of the Cayley Graph Generated by Complete Graph with Missing Edges under the MM$^{\ast }$ Model. (14th November 2019)

• Record Type: Journal Article
• Authors: Ren, Yunxia; Wang, Shiying
• Is Part Of: Computer journal. Volume 63:Number 9(2020)
• Page Start: 1438
• Page End: 1447
• Publication Date: 2019-11-14
• Subjects: interconnection network -- diagnosability -- nest graph; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxz096
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: Diagnosability of a multiprocessor system is an important research topic. The system and an interconnection network have an underlying topology, which is usually presented by a graph. Under the Maeng and Malek's (MM) model, to diagnose the system, a node sends the same task to two of its neighbors, and then compares their responses. The MM$^{*}$ is a special case of the MM model and each node must test all pairs of its adjacent nodes. In 2009, Chiang and Tan (Using node diagnosability to determine $t$ -diagnosability under the comparison diagnosis (cd) model. IEEE Trans. Comput., 58, 251–259) proposed a new viewpoint for fault diagnosis of the system, namely, the node diagnosability. As a new topology structure of interconnection networks, the nest graph $CK_{n}$ has many good properties. In this paper, we study the local diagnosability of $CK_{n}$ and show it has the strong local diagnosability property even if there exist $(\frac{n(n-1)}{2}-2)$ missing edges in it under the MM$^{*}$ model, and the result is optimal with respect to the number of missing edges.