How robust is the n-cube? (Q1104728)

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.