Lehrstuhl Mathematik & InformatikHow Robust is the n-Cube?
Abstract. The n-cube 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 nonfaulty 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 >= 2 is constant, then f(n,k)= \theta (log n). Especially for k=2 and large n: f(n,2) \in [\lceil\alphan\rceil: \lceil\alphan\rceil +2], where \alphan=log n+1/2 log log n+1/2. Or if k=\omega(log log n) then 2k<f(n,k)<2(1+\varepsilon)k, with \varepsilon chosen arbitrary small. The aforementioned upper bounds are obtained by analyzing the behaviour of an adversary who makes ``worst-case'' distributions of a given number of faulty processors. For k=2 the ``worst-case'' distributuion 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.