References

1

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

2

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.

3

L. A. Bassalygo and M. S. Pinsker. Complexity of an optimum nonblocking switching network without reconnections. Problems of Information Transmission, 9:64-66, 1974.

4

F. Chong, E. Egozy, and A. DeHon. Fault tolerance and performance of multipath multistage interconnection networks. In T. F. Knight, Jr. and J. Savage, editors, Advanced Research in VLSI: Proceedings of the MIT/Brown Conference 1992. MIT Press, March 1992. To appear.

5

A. DeHon, T. F. Knight Jr., and H. Minsky. Fault-tolerant design for multistage routing networks. In Proceedings of the International Symposium on Shared Memory Multiprocessing, pages 60-71. Information Processing Society of Japan, April 1991.

6

C. Dwork, D. Peleg, N. Pippenger, and E. Upfal. Byzantine agreement in faulty networks. SIAM Journal on Computing, 17(5):975-988, 1988.

7

S. E. Fahlman. The hashnet interconnection scheme. Technical Report CMU-CS-80-125, Department of Computer Science, Carnegie-Mellon University, Pittsburgh, PA, June 1980.

8

J. Friedman and N. Pippenger. Expanding graphs contain all small trees. Combinatorica, 7(1):71-76, 1987.

9

A. V. Goldberg, B. M. Maggs, and S. A. Plotkin. A parallel algorithm for reconfiguring a multibutterfly network with faulty switches. IEEE Transactions on Computers, 43(3):321-326, March 1994.

10

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.

11

N. Kahale. Better expansion for Ramanujan graphs. In Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, pages 398-404. IEEE Computer Society Press, October 1991.

12

C. Kaklamanis, A. R. Karlin, F. T. Leighton, V. Milenkovic, P. Raghavan, S. Rao, C. Thomborson, and A. Tsantilas. Asymptotically tight bounds for computing with faulty arrays of processors. In Proceedings of the 31st Annual Symposium on Foundations of Computer Science, pages 285-296. IEEE Computer Society Press, October 1990.

13

T. F. Knight, Jr. Technologies for low latency interconnection switches. In Proceedings of the 1989 ACM Symposium on Parallel Algorithms and Architectures, pages 351-358, June 1989.

14

R. R. Koch. Increasing the size of a network by a constant factor can increase performance by more than a constant factor. In Proceedings of the 29th Annual Symposium on Foundations of Computer Science, pages 221-230. IEEE Computer Society Press, October 1988.

15

S. Konstantinidou and E. Upfal. Experimental comparison of multistage networks. IBM Almaden Research Center. Unpublished manuscript, 1991.

16

C. P. Kruskal and M. Snir. The performance of multistage interconnection networks for multiprocessors. IEEE Transactions on Computers, C-32(12):1091-1098, December 1983.

17

C. P. Kruskal and M. Snir. A unified theory of interconnection network structure. Theoretical Computer Science, 48:75-94, 1986.

18

F. T. Leighton. Tight bounds on the complexity of parallel sorting. IEEE Transactions on Computers, C-34(4):344-354, April 1985.

19

F. T. Leighton and B. M. Maggs. Introduction to parallel algorithms and architectures: Expanders PRAMs VLSI. Manuscript in preparation.

20

T. Leighton, C. L. Leiserson, and M. Klugerman. Theory of parallel and VLSI computation. Research Seminar Series Report MIT/LCS/RSS 10, MIT Laboratory for Computer Science, May 1991.

21

T. Leighton, D. Lisinski, and B. Maggs. Empirical evaluation of randomly-wired multistage networks. In Proceedings of the 1990 IEEE International Conference on Computer Design: VLSI in Computers & Processors, pages 380-385. IEEE Computer Society Press, September 1990.

22

C. E. Leiserson. Fat-trees: universal networks for hardware-efficient supercomputing. IEEE Transactions on Computers, C-34(10):892-901, October 1985.

23

A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8(3):261-277, 1988.

24

S. K. Park and K. W. Miller. Random number generators: Good ones are hard to find. Communications of the ACM, 31(10):1192-1201, October 1988.

25

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

26

P. Raghavan. Robust algorithms for packet routing in a mesh. In Proceedings of the 1989 ACM Symposium on Parallel Algorithms and Architectures, pages 344-350, June 1989.

27

R. D. Rettberg, W. R. Crowther, P. P. Carvey, and R. S. Tomlinson. The monarch parallel processor hardware design. Computer, 23(4):18-30, April 1990.

28

C. D. Thompson. A Complexity Theory for VLSI. PhD thesis, Department of Computer Science, Carnegie-Mellon University, Pittsburgh, PA, 1980.

29

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

Frank Thomson Leighton (M'81) received the B.S.E. degree in electrical engineering and computer science from Princeton University in 1978, and the Ph.D. degree in applied mathematics from the Massachusetts Institute of Technology in 1981. He was among the first group of scientists to receive the NSF Presidential Young Investigator award. Currently he is a Professor of Applied Mathematics at the Massachusetts Institute of Technology, and a member of the MIT Laboratory for Computer Science. His research interests include parallel algorithms and architectures, discrete algorithms, VLSI, complexity theory, and combinatorics. He is the editor-in-chief of the Journal of the ACM and also serves on the editorial boards of SIAM Journal on Computing, SIAM Journal on Discrete Mathematics, Journal on Graph Theory, Journal of Algorithms, Cominatorica, and Algorithmica.

Bruce Maggs received the S.B., S.M., and Ph.D., degrees in computer science from the Massachusetts Institute of Technology in 1985, 1986, and 1989, respectively. Currently he is a Research Scientist at the NEC Research Institute in Princeton, NJ. His research interests include parallel computing systems and parallel algorithms.