Adaptive Diagnosis of Variants of the Hypercube

Aya OKASHITA; Toru ARAKI; Yukio SHIBATA

doi:10.1093/ietfec/e88-a.3.728

Adaptive Diagnosis of Variants of the Hypercube

Aya OKASHITA, Toru ARAKI, Yukio SHIBATA

Full Text Views

0

Cite this

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 -log(n + 1).

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

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 -log(n + 1).
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 -log(n + 1).},
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 -log(n + 1).
ER -