How robust is the n-cube?

The n-cube network is called faulty if it contains any faulty processor or any faulty link. For any number k we want to compute the minimum number f(n,k) of faults which is necessary for an adversary to make every (n-k)-dimensional subcube faulty. Reversely formulated: The existence of an (n-k)-dimensional non-faulty subcube can be guaranteed, if there are less than f(n,k) faults in the n-cube. In this paper several lower and upper bounds for f(n,k) are derived such that the resulting gaps are ``small. For instance if \(k\geq 2\) is constant, then \(f(n,k)=\theta (\log n)\). Especially for \(k=2\) and large \(n: f(n,2)\in [\lceil \alpha_ n\rceil: \lceil \alpha_ n\rceil +2],\) where \(\alpha_ n=\log n+\log \log n+\). Or if \(k=\omega (\log \log n)\) then \(2^ k<f(n,k)<2^{(1+\epsilon)^ k}\), with \(\epsilon\) chosen arbitrarily small. The aforementioned upper bounds are obtained by analyzing the behaviour of an adversary who makes ``worst-case distribution of a given number of faulty processors. For \(k=2\) the ``worst-case distribution is obtained constructively. In the general case the constructive methods presented in this paper lead to a (rather ``bad) upper bound which can be significantly improved by probabilistic arguments. The bounds mentioned above change if the notions are relativized with respect to some given parallel fault-checking procedure P. In this case only subcubes which are possible outputs of P must be made faulty by the adversary. The notion of directed chromatic index is defined in order to analyze the case \(k=2\). Relations between the directed chromatic index and the chromatic number are derived, which are of interest in their own right.

Recommendations

Cites work

Cited in

(22)

This page was built for publication: How robust is the n-cube?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1104728)