Pancake网络的t/k-诊断度及其算法  

The t/k-diagnosability and diagnosis algorithm of Pancake networks

作　　者：宋苏琳 林丽美[1] 周书明[1,2] 

机构地区：[1]福建师范大学数学与计算机科学学院,福州350007 [2]福建师范大学网络安全与密码技术重点实验室,福州350007

出　　处：《运筹学学报》2014年第4期65-77,共13页Operations Research Transactions

基　　金：福建省教育厅A类基金(No.JA12073);福建省自然科学基金(No.2013J01221);福建师范大学"网络与信息安全关键理论和技术"校创新团队(No.IRTL1207)

摘　　要：由于大型多处理机系统规模的不断扩大,其组件脆弱性也随之增加,因此故障容错性能对于多处理机系统尤为重要.t/k-诊断分析是一种能极大提高多处理机系统自我诊断性能的系统级故障诊断策略,该诊断策略能识别至多t个故障处理机节点,其中可能包含至多k个被误诊的处理机.首先给出了Pancake网络P_n(n≥5)的容错性分析,其后证明了P_n在PMC模型下是((k+1)n-3k-1)/k-可诊断的,其中1≤k≤3,最后还给出复杂度为O(NlogN)的快速诊断算法来识别所有的故障节点.Fault tolerance is especially important for multiprocessor system since the growing size of the multiprocessor system increases its vulnerability to component failures. The t/k-diagnosis is a kind of diagnostic strategy at system level that can significantly enhance the multiprocessor system＇s self-diagnosing capability. It can detect up to t faulty processors （or nodes, units） which might include at most k misdiagnosed processors, This paper first explores the fault tolerance of Pancake networks Pn （n ≥ 5）, and then proves that Pn is （（k ＋ 1）n - 3k - 1）/k-diagnosable under the PMC model, 1 ≤k ≤ 3. Finally it proposes a quick diagnosis algorithm with complexity O（NlogN） to identify all the faulty nodes.

关 键 词：Pancake网络 容错性 t/k-诊断度 诊断算法 

分 类 号：O157.5[理学—数学]