Fast algorithms for bit-serial routing on a hypercube


Journal Article

In this paper, we describe an O(log N) bit-step randomized algorithm for bit-serial message routing on a hypercube. The result is asymptotically optimal, and improves upon the best previously known algorithms by a logarithmic factor. The result also solves the problem of on-line circuit switching in an O(1)-dilated hypercube (i.e., partitioning the edges of a dilated hypercube so as to realize an arbitrary permutation of point-to-point connections between the nodes). Our algorithm is adaptive and we show that this is necessary to achieve the logarithmic speedup. We generalize the Borodin-Hopcroft lower bound on oblivious routing by proving that any oblivious randomized algorithm on a polylogarithmic degree network requires Ω(log2 N/log log N) bit steps with high probability for almost all permutations.

Duke Authors

Cited Authors

  • Aiello, B; Leighton, T; Maggs, B; Newman, M

Published Date

  • December 1, 1990

Published In

  • Algorithms and Architectures

Start / End Page

  • 55 - 64

Citation Source

  • Scopus