Erik D. Demaine, Ian Foster, et al.
IEEE TPDS
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.
Erik D. Demaine, Ian Foster, et al.
IEEE TPDS
Hagit Attiya, Marc Snir, et al.
Journal of the ACM
Sergio Felperin, Prabhakar Raghavan, et al.
FOCS 1992
Uriel Feige, David Peleg, et al.
Random Structures and Algorithms