Fast fault‐tolerant parallel communication for de bruijn and digit‐exchange networks using information dispersal
Yuh‐Dauh Lyuu · Networks · 1993
Abstract In this paper, the space‐efficient Information Dispersal Algorithm (IDA) is applied to fault‐tolerant parallel communication in the de Bruijn andd‐way digit‐exchange networks, which is a generalized butterfly (Omega) network. LetN=dndenote 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). Ford= [nInn], it probability of successful routing is at least 1 −N−InN/2. The scheme also toleratesO(N)random link failures with probability at least 1 −N(7−InInn)/6. We also propose a routing scheme for the d‐way digit‐exchange network such that similar bounds hold. Both schemes run within the said time bounds without queuing delay. ©1993 by John Wiley & Sons, Inc.