IEICE TRANSACTIONS on Fundamentals
Adaptive Diagnosis of Variants of the Hypercube
Summary :
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 n + 1 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 n -
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E88-A No.3 pp.728-735
- Publication Date
- 2005/03/01
- Publicized
- Online ISSN
- DOI
- 10.1093/ietfec/e88-a.3.728
- Type of Manuscript
- PAPER
- Category
- Graphs and Networks
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Aya OKASHITA, Toru ARAKI, Yukio SHIBATA, "Adaptive Diagnosis of Variants of the Hypercube" in IEICE TRANSACTIONS on Fundamentals,
vol. E88-A, no. 3, pp. 728-735, March 2005, doi: 10.1093/ietfec/e88-a.3.728.
Abstract: 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 n + 1 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 n -
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e88-a.3.728/_p
Copy
@ARTICLE{e88-a_3_728,
author={Aya OKASHITA, Toru ARAKI, Yukio SHIBATA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Adaptive Diagnosis of Variants of the Hypercube},
year={2005},
volume={E88-A},
number={3},
pages={728-735},
abstract={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 n + 1 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 n -
keywords={},
doi={10.1093/ietfec/e88-a.3.728},
ISSN={},
month={March},}
Copy
TY - JOUR
TI - Adaptive Diagnosis of Variants of the Hypercube
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 728
EP - 735
AU - Aya OKASHITA
AU - Toru ARAKI
AU - Yukio SHIBATA
PY - 2005
DO - 10.1093/ietfec/e88-a.3.728
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E88-A
IS - 3
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - March 2005
AB - 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 n + 1 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 n -
ER -
English
