Reliability of Hypercubes for Broadcasting with Random Faults

Feng BAO; Yoshihide IGARASHI; Sabine R. OHRING

Reliability of Hypercubes for Broadcasting with Random Faults

Feng BAO, Yoshihide IGARASHI, Sabine R. OHRING

Full Text Views

0

Cite this

Summary :

In this paper we analyze the reliability of a simple broadcasting scheme for hypercubes (HCCAST) with random faults. We prove that HCCAST (n) (HCCAST for the n-dimensional hypercube) can tolerate Θ(2ⁿ/n) random faulty nodes with a very high probability although it can tolerate only n - 1 faulty nodes in the worst case. By showing that most of the f-fault configurations of the n dimensional hypercube cannot make HCCAST (n) fail unless f is too large, we illustrate that hypercubes are inherently strong enough for tolerating random faults. For a realistic n, the reliability of HCCAST (n) is much better than that of the broadcasting algorithm described in [6] although the latter can asymptotically tolerate faulty links of a constant fraction of all the links. Finally, we compare the fault-tolerant performance of the two broadcasting schemes for n = 15, 16, 17, 18, 19, 20, and we find that for those practical valuse, HCCAST (n) is very reliable.

Publication: IEICE TRANSACTIONS on Information Vol.E79-D No.1 pp.22-28

Publication Date: 1996/01/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Fault Tolerant Computing

Cite this

Copy

Feng BAO, Yoshihide IGARASHI, Sabine R. OHRING, "Reliability of Hypercubes for Broadcasting with Random Faults" in IEICE TRANSACTIONS on Information, vol. E79-D, no. 1, pp. 22-28, January 1996, doi: .
Abstract: In this paper we analyze the reliability of a simple broadcasting scheme for hypercubes (HCCAST) with random faults. We prove that HCCAST (n) (HCCAST for the n-dimensional hypercube) can tolerate Θ(2ⁿ/n) random faulty nodes with a very high probability although it can tolerate only n - 1 faulty nodes in the worst case. By showing that most of the f-fault configurations of the n dimensional hypercube cannot make HCCAST (n) fail unless f is too large, we illustrate that hypercubes are inherently strong enough for tolerating random faults. For a realistic n, the reliability of HCCAST (n) is much better than that of the broadcasting algorithm described in [6] although the latter can asymptotically tolerate faulty links of a constant fraction of all the links. Finally, we compare the fault-tolerant performance of the two broadcasting schemes for n = 15, 16, 17, 18, 19, 20, and we find that for those practical valuse, HCCAST (n) is very reliable.
URL: https://global.ieice.org/en_transactions/information/10.1587/e79-d_1_22/_p

Copy

@ARTICLE{e79-d_1_22,
author={Feng BAO, Yoshihide IGARASHI, Sabine R. OHRING, },
journal={IEICE TRANSACTIONS on Information},
title={Reliability of Hypercubes for Broadcasting with Random Faults},
year={1996},
volume={E79-D},
number={1},
pages={22-28},
abstract={In this paper we analyze the reliability of a simple broadcasting scheme for hypercubes (HCCAST) with random faults. We prove that HCCAST (n) (HCCAST for the n-dimensional hypercube) can tolerate Θ(2ⁿ/n) random faulty nodes with a very high probability although it can tolerate only n - 1 faulty nodes in the worst case. By showing that most of the f-fault configurations of the n dimensional hypercube cannot make HCCAST (n) fail unless f is too large, we illustrate that hypercubes are inherently strong enough for tolerating random faults. For a realistic n, the reliability of HCCAST (n) is much better than that of the broadcasting algorithm described in [6] although the latter can asymptotically tolerate faulty links of a constant fraction of all the links. Finally, we compare the fault-tolerant performance of the two broadcasting schemes for n = 15, 16, 17, 18, 19, 20, and we find that for those practical valuse, HCCAST (n) is very reliable.},
keywords={},
doi={},
ISSN={},
month={January},}

Copy

TY - JOUR
TI - Reliability of Hypercubes for Broadcasting with Random Faults
T2 - IEICE TRANSACTIONS on Information
SP - 22
EP - 28
AU - Feng BAO
AU - Yoshihide IGARASHI
AU - Sabine R. OHRING
PY - 1996
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E79-D
IS - 1
JA - IEICE TRANSACTIONS on Information
Y1 - January 1996
AB - In this paper we analyze the reliability of a simple broadcasting scheme for hypercubes (HCCAST) with random faults. We prove that HCCAST (n) (HCCAST for the n-dimensional hypercube) can tolerate Θ(2ⁿ/n) random faulty nodes with a very high probability although it can tolerate only n - 1 faulty nodes in the worst case. By showing that most of the f-fault configurations of the n dimensional hypercube cannot make HCCAST (n) fail unless f is too large, we illustrate that hypercubes are inherently strong enough for tolerating random faults. For a realistic n, the reliability of HCCAST (n) is much better than that of the broadcasting algorithm described in [6] although the latter can asymptotically tolerate faulty links of a constant fraction of all the links. Finally, we compare the fault-tolerant performance of the two broadcasting schemes for n = 15, 16, 17, 18, 19, 20, and we find that for those practical valuse, HCCAST (n) is very reliable.
ER -