FAST FAULT-TOLERANT PARALLEL COMMUNICATION FOR DEBRUIJN AND DIGIT-EXCHANGE NETWORKS USING INFORMATION DISPERSAL

In this paper, the space-efficient Information Dispersal Algorithm (ID A) is applied to fault-tolerant parallel communication in the de Bruij n and d-way digit-exchange networks, which is a generalized butterfly (Omega) network. Let N = d(n) denote the size of the de Bruijn network . Our routing scheme runs in 2n + 1 time using constant size buffers ( if the routing information is not counted). For d = [n In n], it proba bility of successful routing is at least 1 - N(-ln N/2). The scheme al so tolerates O(N) random link failures with probability at least 1 - N (7-lnlnn)/6. We also propose a routing scheme for the d-way digit-exch ange network such that similar bounds hold. Both schemes run within th e said time bounds without queuing delay.