Skip to main content

Fast algorithms for bit-serial routing on a hypercube

Publication ,  Journal Article
Aiello, B; Leighton, T; Maggs, B; Newman, M
Published in: Algorithms and Architectures
January 1, 1990

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 Scholars

Published In

Algorithms and Architectures

DOI

Publication Date

January 1, 1990

Start / End Page

55 / 64
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Aiello, B., Leighton, T., Maggs, B., & Newman, M. (1990). Fast algorithms for bit-serial routing on a hypercube. Algorithms and Architectures, 55–64. https://doi.org/10.1145/97444.97459
Aiello, B., T. Leighton, B. Maggs, and M. Newman. “Fast algorithms for bit-serial routing on a hypercube.” Algorithms and Architectures, January 1, 1990, 55–64. https://doi.org/10.1145/97444.97459.
Aiello B, Leighton T, Maggs B, Newman M. Fast algorithms for bit-serial routing on a hypercube. Algorithms and Architectures. 1990 Jan 1;55–64.
Aiello, B., et al. “Fast algorithms for bit-serial routing on a hypercube.” Algorithms and Architectures, Jan. 1990, pp. 55–64. Scopus, doi:10.1145/97444.97459.
Aiello B, Leighton T, Maggs B, Newman M. Fast algorithms for bit-serial routing on a hypercube. Algorithms and Architectures. 1990 Jan 1;55–64.

Published In

Algorithms and Architectures

DOI

Publication Date

January 1, 1990

Start / End Page

55 / 64