Compared with accurate diagnosis, the system’s selfdiagnosing capability can be greatly increased through the t/kdiagnosis strategy at most k vertexes to be mistakenly identified as faulty under the comparison model,...Compared with accurate diagnosis, the system’s selfdiagnosing capability can be greatly increased through the t/kdiagnosis strategy at most k vertexes to be mistakenly identified as faulty under the comparison model, where k is typically a small number. Based on the Preparata, Metze, and Chien(PMC)model, the n-dimensional hypercube network is proved to be t/kdiagnosable. In this paper, based on the Maeng and Malek(MM)*model, a novel t/k-fault diagnosis(1≤k≤4) algorithm of ndimensional hypercube, called t/k-MM*-DIAG, is proposed to isolate all faulty processors within the set of nodes, among which the number of fault-free nodes identified wrongly as faulty is at most k. The time complexity in our algorithm is only O(2~n n~2).展开更多
An interconnection network＇s diagnosability is an important metric for measuring its self-diagnostic capability. Permanent fault and intermittent fault are two different fault models that exist in an interconnection ...An interconnection network＇s diagnosability is an important metric for measuring its self-diagnostic capability. Permanent fault and intermittent fault are two different fault models that exist in an interconnection network. In this paper, we focus on the problem pertaining to the diagnosability of interconnection networks in an intermittent fault situation. First, we study a class of interconnection networks called crisp three-cycle networks, in which the Chin-number （the number of common vertices each pair of vertices share） is no more than one. Necessary and sufficient conditions are derived for the diagnosability of crisp three-cycle networks under the PMC （Preparata, Metze, and Chien） model. A simple check can show that many well-known intereonnection networks are crisp three-cycle networks. Second, we prove that an intereonnection network S is a ti-fault diagnosable system without repair if and only if its minimum in-degree is greater than ti under the BGM （Barsi, Grandoni, and Masetrini） model. Finally, we extend the necessary and sufficient conditions to determine whether an interconnection network S is ti-fault diagnosable without repair under the MM （Maeng and Malek） model from the permanent fault situation to the intermittent fault situation.展开更多
基金supported by the National Natural Science Foundation of China(61363002)
文摘Compared with accurate diagnosis, the system’s selfdiagnosing capability can be greatly increased through the t/kdiagnosis strategy at most k vertexes to be mistakenly identified as faulty under the comparison model, where k is typically a small number. Based on the Preparata, Metze, and Chien(PMC)model, the n-dimensional hypercube network is proved to be t/kdiagnosable. In this paper, based on the Maeng and Malek(MM)*model, a novel t/k-fault diagnosis(1≤k≤4) algorithm of ndimensional hypercube, called t/k-MM*-DIAG, is proposed to isolate all faulty processors within the set of nodes, among which the number of fault-free nodes identified wrongly as faulty is at most k. The time complexity in our algorithm is only O(2~n n~2).
文摘An interconnection network＇s diagnosability is an important metric for measuring its self-diagnostic capability. Permanent fault and intermittent fault are two different fault models that exist in an interconnection network. In this paper, we focus on the problem pertaining to the diagnosability of interconnection networks in an intermittent fault situation. First, we study a class of interconnection networks called crisp three-cycle networks, in which the Chin-number （the number of common vertices each pair of vertices share） is no more than one. Necessary and sufficient conditions are derived for the diagnosability of crisp three-cycle networks under the PMC （Preparata, Metze, and Chien） model. A simple check can show that many well-known intereonnection networks are crisp three-cycle networks. Second, we prove that an intereonnection network S is a ti-fault diagnosable system without repair if and only if its minimum in-degree is greater than ti under the BGM （Barsi, Grandoni, and Masetrini） model. Finally, we extend the necessary and sufficient conditions to determine whether an interconnection network S is ti-fault diagnosable without repair under the MM （Maeng and Malek） model from the permanent fault situation to the intermittent fault situation.
