Total exchange in faulty SIMD hypercubes

We develop algorithms for performing total exchange (all-to-all broadcast) in an n-dimensional faulty SIMD hypercube, Q_n, with up to n-1 node faults. In an SIMD hypercube, during a communication step, nodes can exchange information with their neighbors only across a specific dimension. We describe a sequence of algorithms which take N log N, N log n, 3N-7, 2.5N-7 steps for this problem. By carefully analyzing these algorithms and a property of certain ordering of dimensions, we obtain an improved algorithm which takes 2N steps