Hagit Attiya, Marc Snir
Journal of Algorithms
We study in this paper the use of randomized routing in multistage networks. While log N additional randomizing stages are needed to break "spatial localitywithin each permutation, only log log N additional randomizing stages are needed to break "temporal locality" among successive permutations. Thus, log N bits of initial randomization per input, followed by log log N bits of randomization per packet are sufficient to ensure that t permutations are delivered in time t + log N. We present simulation results that validate this analysis. ©1996 IEEE.
Hagit Attiya, Marc Snir
Journal of Algorithms
Andrei Z. Broder, Alan M. Frieze, et al.
STOC 1992
Jack J. Dongarra, Steve W. Otto, et al.
Communications of the ACM
Prabhakar Raghavan, Eli Upfal
STOC 1994