The traditional, well-known system-level fault diagnosis is to precisely identify faulty nodes in a network via mutual testing between the nodes, and thediagnosabilityis the maximum allowed number of faulty nodes for correct diagnosis.This paper proposes a new scheme that focuses on detecting whether a given critical substructure (e.g., a specific cycle or path) contains any faulty node. If the detecting outcome is “Yes”, the entire substructure is deemed as faulty, regardless of how many faulty nodes, and where they are in the substructure. This approach is often more cost-effective and technically feasible than pinpointing every faulty node. We name the maximum allowed number of faulty nodes for this strategy to work as theDetectabilityof the network, as opposed to the diagnosability.We study the detectability for the hypercube$Qn$, under the PMC model. We will show that in$Qn$(n ≥ 7), the detectability is2n − 1for the minimal bipartite subgraphK1,1, and4n − 5for the 4-node cycleC4. Notably, detectability consistently exceeds traditional diagnosability, tolerating more faulty nodes. We have also designed, validated, and implemented detection algorithms ofO(n·2n−1)complexity to detect faultyK1,1andC4inQn. Simulations show a 100% detection rate, with effectiveness maintained even in lower-dimensionalQnwhere theoretical assumptions do not fully hold.

Abstract Connectivity and diagnosability are widely recognized as crucial parameters for assessing the reliability of multiprocessor systems. Traditionally, connectivity has been classified into two distinct types: node connectivity and edge connectivity. In addition, system-level fault diagnosis theories have typically assumed that communication link faults do not occur, disregarding the potential coexistence of processor failures and communication link faults. In this paper, we propose a novel hybrid model called the HPMC* (Hybrid Preparata, Metze, and Chien) model, which no longer adheres to the stringent assumptions. We introduce the concepts of hybrid connectivity and super hybrid connectivity, and determine the hybrid connectivity of general graphs as well as the super hybrid connectivity of bijective connection (BC) networks. Motivated by these connectivity concepts, we present two novel hybrid fault diagnosis strategies: node-edge hybrid diagnosability and conditional node-edge hybrid diagnosability. These theories address the simultaneous diagnosis of node and edge faults, improving fault diagnosis capability of multiprocessor systems. Additionally, we determine the node-edge hybrid diagnosability of general graphs under the HPMC* model and develop an effective node-edge hybrid $t$-diagnosis algorithm. Finally, we establish a relationship between conditional node-edge hybrid diagnosability and super hybrid connectivity. As a result, we determine the conditional node-edge hybrid diagnosabilities of BC networks.

Wireless sensor networks (WSNs) often utilize virtual backbones (VBs) to optimize routing and reduce energy consumption. The effectiveness of this optimization largely depends on the size of the VB, with smaller VBs offering better performance. In WSNs, VBs are typically modeled as connected dominating sets (CDSs) within unit disk graphs (UDGs). However, existing approximation algorithms for constructing the minimum connected dominating set (MCDS) often introduce redundant dominators, leading to inflated CDSs. To tackle this issue, in this paper, we propose a general CDS optimization algorithm named OP-CDS, designed specifically to minimize redundancies. Theoretical analysis shows that the size of the optimized CDS is bounded by α∙opt+δ-k+1, where α∙opt+δ represents the upper bound of the unoptimized CDS, and k denotes the number of OP-CDS iterations. Additionally, extensive simulations demonstrate that OP-CDS can effectively optimize the CDS generated by state-of-the-art algorithms with minimal time consumption.

The Hamiltonian path serves as a robust tool for unicast or multicast communication in parallel and distributed systems. Embedding this path structure into large-scale systems, especially those with numerous failures, remains a formidable and pressing challenge. The arrangement graph is a topology that not only generalizes many renowned network architectures but is also a promising framework for future computer systems. Extensive research has been conducted on the fault-tolerant embedding of Hamiltonian paths in the arrangement graph or its subclasses, yet these efforts have not attained the desired fault tolerance levels. In this article, we focus on significantly improving the edge fault-tolerant embedding capabilities of arrangement graphs by adopting a novel fault model, termed the partitioned edge fault model. We first prove the existence of Hamiltonian path avoiding large-scale edge faults in arrangement graphs. Then we develop a corresponding Hamiltonian path embedding algorithm with high fault-tolerant capability for arrangement graphs. Both theoretical comparisons and experimental analyses reveal that our methods yield significant enhancements in fault tolerance over existing studies. Furthermore, building upon the generated Hamiltonian path, we devise a dual-path multicast routing strategy and evaluate its latency performance.

Abstract Diagnosability is often considered as an important factor for measuring the self-diagnostic ability of network systems. However, classic system-level diagnosis focuses only on processor faults and ignores the objective reality of communication faults. Under real circumstances, missing edges and node failures usually occur simultaneously in multiprocessor systems (called hybrid fault circumstances). Therefore, it is important to study the diagnosability of multiprocessor systems under hybrid fault circumstances. In this paper, we propose several diagnosabilities of interconnection networks with missing edges and faulty nodes. By exploring some important relationships between diagnosability and the minimum degree of a network under hybrid fault circumstances, we present and prove the diagnosability of several classic interconnection networks, including BC (bijective connection) networks, star graphs, folded hypercubes, exchanged hypercubes, exchanged crossed cubes, k-ary n-cubes, bubble-sort star graphs and balanced hypercubes, with missing edges and broken-down nodes under the PMC (Preparata, Metze and Chien) and MM* (Maeng and Malek) models.