The Extra, Restricted Connectivity and Conditional Diagnosability of Split-Star Networks

Limei Lin, Li Xu, Shuming Zhou, Sun Yuan Hsieh

Research output: Contribution to journalArticlepeer-review

44 Citations (Scopus)


Connectivity is a classic measure for fault tolerance of a network in the case of vertices failures. Extra connectivity and restricted connectivity are two important indicators of the robustness of a multi-processor system in presence of failing processors. An interconnection network's diagnosability is an important measure of its self-diagnostic capability. The conditional diagnosability is widely accepted as a new measure of diagnosability by assuming that any fault-set cannot contain all neighbors of any node in a multiprocessor system. In this paper, we analyze the combinatorial properties and fault tolerance ability for the Split-Star Network, denoted by Sn2, a well-known interconnection network proposed for multiprocessor systems, establish the g -extra connectivity, where 1\le g\le 3. We also determine the h-restricted connectivity (h=1,2), and prove that the conditional diagnosability of Sn2 (n\ge 4) is 6n-16 under the comparison model, which is about three times of the Sn2 's traditional diagnosability. As a product, the strong diagnosability of Sn2 is also obtained.

Original languageEnglish
Article number7031970
Pages (from-to)533-545
Number of pages13
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number2
Publication statusPublished - 2016 Feb 1

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'The Extra, Restricted Connectivity and Conditional Diagnosability of Split-Star Networks'. Together they form a unique fingerprint.

Cite this