PMC模式下超立方體的條件偵錯能力

Abstract

在多處理器系統中，偵錯能力是一個判斷其系統可靠度的重要指標。在研究中我們發現，許多Ｎ正則圖形的偵錯能力為Ｎ，是因為當某一點的所有鄰居同時皆為壞點時，則系統將無法正確進行診斷，一般情況下此情形發生機率是很低的。所以在此，我們藉由要求一個系統中的壞點集合不可包含任一點的所有鄰居，定義出條件偵錯能力。在本篇論文中，我們證明了超立方體在ＰＭＣ模式下的條件偵錯能力為4(n-2)+1。

The diagnosability is an important role to value the reliability of an interconnection networks. We introduce a new measure of conditional diagnosability by requiring any faulty set cannot contain all the neighbors of any vertex in the graph. Based on this measure, the conditional connectivity of Hypercube is shown to be 4(n-2)+1 under the PMC model.