The Diagnosability of Interconnection Networks with Missing Edges and Broken-Down Nodes Under the PMC and MM^* Models.

This article focuses on the diagnosability of multiprocessor interconnection networks under hybrid fault conditions, where both processor (node) faults and communication (edge) faults occur simultaneously. It introduces sufficient conditions relating the diagnosability of a network with missing edges and broken-down nodes to the network’s minimum degree, and establishes exact diagnosability results under the Preparata, Metze and Chien (PMC) and Maeng and Malek (MM*) models. The paper applies these theoretical results to various classic interconnection networks—including BC networks, star graphs, folded hypercubes, exchanged hypercubes, exchanged crossed cubes, k-ary n-cubes, bubble-sort star graphs, and balanced hypercubes—demonstrating that their diagnosability with hybrid faults equals the minimum degree of the surviving network. The study highlights the importance of considering both node and link faults for reliable system-level diagnosis and suggests future work on diagnosability involving intermittent faults.