Reliability of Hypercubes for Broadcasting with Random Faults

概要

論文の詳細を見る
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/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 can-not 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 values, HCCAST (n) is very reliable.
社団法人電子情報通信学会の論文
1996-01-25