MISC

2005年3月

Adaptive diagnosis of variants of the hypercube

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES
  • A Okashita
  • ,
  • T Araki
  • ,
  • Y Shibata

E88A
3
開始ページ
728
終了ページ
735
記述言語
英語
掲載種別
DOI
10.1093/ietfec/e88-a.3.728
出版者・発行元
IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG

System-level fault diagnosis deals with the problem of identifying faulty nodes (processors) in a multiprocessor system. Each node is faulty or fault-free, and it can test other nodes in the system, and outputs the test results. The test result from a node is reliable if the node is fault-free, but the result is unreliable if it is faulty. In this paper, we prove that four variants of the hypercube: the crossed cube, the twisted cube, the Mobius cube, and the enhanced cube, are adaptively diagnosed using at most 4 parallel testing rounds, with at most n faulty nodes (for the enhanced cube, with at most n + 1 faulty nodes), where each processor participates in at most one test in each round. Furthermore, we propose another diagnosis algorithm for the n-dimensional enhanced cube with at most it + I faulty nodes, and show that it is adaptively diagnosed with at most 5 rounds in the worst case, but with at most 3 rounds if the number of existing faulty nodes is at most it - [log(n + 1)].

Web of Science ® 被引用回数 : 3

リンク情報
DOI
https://doi.org/10.1093/ietfec/e88-a.3.728
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000227828700015&DestApp=WOS_CPL

エクスポート
BibTeX RIS