References

1

W. Aiello and T. Leighton. Coding theory, hypercube embeddings, and fault tolerance. In Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures, pages 125-136, July 1991.

2

M. Ajtai, J. Komlós, and E. Szemerédi. Sorting in parallel steps. Combinatorica, 3:1-19, 1983.

3

R. Aleliunas. Randomized parallel communication. In Proceedings of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pages 60-72, August 1982.

4

S. Arora, T. Leighton, and B. Maggs. On-line algorithms for path selection in a non-blocking network. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, pages 149-158, May 1990.

5

K. Batcher. Sorting networks and their applications. In Proceedings of the AFIPS Spring Joint Computing Conference, volume 32, pages 307-314, 1968.

6

V. E. Benes. Mathematical Theory of Connecting Networks and Telephone Traffic. Academic Press, New York, 1965.

7

A. Borodin and J. E. Hopcroft. Routing, merging, and sorting on parallel models of computation. Journal of Computer and System Sciences, 30(1):130-145, February 1985.

8

R. E. Cypher. Efficient Communication in Massively Parallel Computers. PhD thesis, University of Washington, Department of Computer Science, Seattle, WA, August 1989.

9

R. E. Cypher and C. G. Plaxton. Techniques for shared key sorting. Unpublished manuscript.

10

R. E. Cypher and C. G. Plaxton. Deterministic sorting in nearly logarithmic time on the hypercube and related computers. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, pages 193-203, May 1990.

11

W. Dally and C. Seitz. Deadlock free message routing in multiprocessor interconnection networks. IEEE Transactions on Computers, C-36(5):547-553, May 1987.

12

D. S. Greenberg and S. N. Bhatt. Routing multiple paths in hypercubes. In Proceedings of the 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, pages 45-54, July 1990.

13

R. W. Hamming. Error detecting and error correcting codes. Bell System Technical Journal, 29:147-160, 1950.

14

J. Hastad, T. Leighton, and M. Newman. Fast computation using faulty hypercubes. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pages 251-263, May 1989.

15

C. Kaklamanis, D. Krizanc, and A. Tsantilas. Tight bounds for oblivous routing in the hypercube. In Proceedings of the 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, pages 31-36, July 1990.

16

P. Kermani and L. Kleinrock. Virtual cut-through: a new computer communications switching technique. Computer Networks, 3(4):267-286, 1979.

17

D. Krizanc, D. Peleg, and E. Upfal. A time-randomness tradeoff for oblivous routing. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, pages 93-102, May 1988.

18

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

19

T. Leighton, B. Maggs, and S. Rao. Universal packet routing algorithms. In Proceedings of the 29th Annual Symposium on Foundations of Computer Science, pages 256-271, October 1988.

20

T. Leighton and G. Plaxton. A (fairly) simple circuit that (usually) sorts. In Proceedings of the 31st Annual Symposium on Foundations of Computer Science, pages 264-274. IEEE Computer Society Press, October 1990.

21

D. Nassimi and S. Sahni. Parallel algorithms to set up the Benes permutation network. IEEE Transactions on Computers, C-31(2):148-154, February 1982.

22

M. O. Rabin. Efficient dispersal of information for security, load balancing, and fault tolerance. Journal of the ACM, 36(2), April 1989.

23

A. G. Ranade. How to emulate shared memory. In Proceedings of the 28th Annual Symposium on Foundations of Computer Science, pages 185-194. IEEE Computer Society Press, October 1987.

24

E. Upfal. Efficient schemes for parallel communication. In Proceedings of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pages 55-59, August 1982.

25

E. Upfal. An deterministic packet routing scheme. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pages 241-250, May 1989.

26

L. G. Valiant. A scheme for fast parallel communication. SIAM Journal on Computing, 11(2):350-361, May 1982.

27

L. G. Valiant and G. J. Brebner. Universal schemes for parallel communication. In Proceedings of the 13th Annual ACM Symposium on Theory of Computing, pages 263-277, May 1981.