Reliability evaluation of complete cubic networks. Issue 1 (2nd January 2020)

• Record Type: Journal Article
• Authors: Sun, Xueli; Zhou, Shuming; Gu, Zhendong; Wang, Yihong; Li, Min
• Is Part Of: International journal of parallel, emergent and distributed systems. Volume 35:Issue 1(2020)
• Page Start: 42
• Page End: 56
• Publication Date: 2020-01-02
• Subjects: g-extra connectivity -- g-extra diagnosability -- t/k-diagnosability -- complete cubic networks; Parallel computers -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; Computer algorithms -- Periodicals; 004.35
• DOI: 10.1080/17445760.2019.1658193
• Languages: English
• ISSNs: 1744-5760

Abstract

Abstract : Fault diagnostic analysis is extremely important for interconnection networks. Given a graph G and a positive integer g, the g -extra connectivity of G (denoted by κ o ( g ) ( G ) ) is the minimum cardinality of a subset S of V ( G ) such that G − S is disconnected and every remaining component has at least g + 1 vertices. The g -extra diagnosability of G (denoted by t ~ g ( G ) ), is the maximum number of faulty vertices that the system can guarantee to identify under the condition that every fault-free component contains at least g + 1 vertices. The t / k -diagnosis strategy can detect up to t faulty vertices which might include at most k misdiagnosed vertices. In this paper, we first determine κ o ( g ) ( C C N ( n ) ) = ( g + 1 ) n − g + 1 2 + 1 for n ≥ 2, 1 ≤ g ≤ n − 1, where C C N ( n ) is an n -dimensional complete cubic network, which generalises the hierarchical cubic network. Moreover, we establish t ~ g ( C C N ( n ) ) = ( g + 1 ) ( n + 1 ) − g + 1 2 under the PMC model ( n ≥ 4, 1 ≤ g ≤ n − 3 ) and under the MM* model ( n ≥ 6, 1 ≤ g ≤ ( n − 2 ) / 4 ), respectively. Furthermore, we show that C C N ( n ) is [ ( k + 1 ) n − k + 1 2 + 1 ] / k -diagnosable under the PMC model. As a consequence, we also derive the related results of the n -dimensional hierarchical cubic network H C N n . GRAPHICAL ABSTRACT: