| Pancake网络的t/k-诊断度及其算法 |
| |
| 引用本文： | 宋苏琳,林丽美,周书明.Pancake网络的t/k-诊断度及其算法[J].运筹学学报,2014,18(4):65-77. |
| |
| 作者姓名： | 宋苏琳 林丽美 周书明 |
| |
| 作者单位： | 1. 福建师范大学数学与计算机科学学院, 福州 350007; 2. 福建师范大学网络安全与密码技术重点实验室, 福州 350007 |
| |
| 基金项目： | 福建省教育厅A类基金(No.JA12073);福建省自然科学基金(No.2013J01221);福建师范大学“网络与信息安全关键理论和技术”校创新团队(No.IRTL1207) |
| |
| 摘 要： | 由于大型多处理机系统规模的不断扩大, 其组件脆弱性也随之增加, 因此故障容错性能对于多处理机系统尤为重要. t/k-诊断分析是一种能极大提高多处理机系统自我诊断性能的系统级故障诊断策略，该诊断策略能识别至多t个故障处理机节点, 其中可能包含至多$k$个被误诊的处理机. 首先给出了Pancake网络P_n(n\geq 5) 的容错性分析, 其后证明了P_n在PMC模型下是((k+1)n-3k-1)/k-可诊断的, 其中1\leq k\leq 3, 最后还给出复杂度为O(NlogN)的快速诊断算法来识别所有的故障节点.
|
| 关 键 词： | Pancake网络 容错性 t/k-诊断度 诊断算法 |
| 收稿时间： | 2014-04-09 |
The t/k-diagnosability and diagnosis algorithm of Pancake networks |
| |
| SONG Sulin,LIN Limei,ZHOU Shuming.The t/k-diagnosability and diagnosis algorithm of Pancake networks[J].OR Transactions,2014,18(4):65-77. |
| |
| Authors: | SONG Sulin LIN Limei ZHOU Shuming |
| |
| Affiliation: | 1. School of Mathematics and Computer Science, Fujian Normal University, Fuzhou 350007, China; 2. Fujian Provincial Key Laboratory of Network Security and Cryptology, Fujian Normal University, Fuzhou 350007, China |
| |
| Abstract: | 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 P_n (n\geq 5), and then proves that P_n is ((k+1)n-3k-1)/k-diagnosable under the PMC model, 1\leq k\leq 3 Finally it proposes a quick diagnosis algorithm with complexity O(NlogN) to identify all the faulty nodes. |
| |
| Keywords: | Pancake networks fault tolerance t/k-diagnosability diagnosis algorithm |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
|
点击此处可从《运筹学学报》下载全文 |
