• Randomized routing and sorting on fixed-connection networks. F. T. Leighton, B. M. Maggs, S. B. Rao, and A. G. Ranade, Journal of Algorithms, Vol. 17, No. 1, July 1994, pp. 157-205.

  This paper presents a randomized on-line algorithm for scheduling any set of N packets whose paths are fixed and have congestion c on any bounded-degree leveled network with depth L. With high probability, the algorithm delivers the packets to their destinations in O(c+L+log N) steps, using constant-size queues. The scheduling algorithm yields the first algorithm for routing permutations of N packets on the shuffle-exchange network in O(log N) steps using constant-size queues, for sorting on butterfly and shuffle-exchange networks in O(log N) steps using constant-size queues, and for routing and sorting on N^k-node multidimensional arrays in O(kN) steps using constant-size queues. The algorithm also leads to the construction of an area-universal network: an N-node network with area Theta(N) that can simulate any other network of area O(N) with slowdown O(log N).

  HTML Postscript Compressed Postscript
  Back to other publications

  Back to my home page