Non-Blocking Networks

Authors

Paul Feldman, Massachusetts Institute of Technology
Joel Friedman, University of California - Berkeley
Nicholas Pippenger, Harvey Mudd CollegeFollow

Document Type

Article

Department

Mathematics (HMC)

Publication Date

1986

Abstract

Two variants of the concept "non-blocking" have been defined in the literature: "strictly" non-blocking and "wide-sense" non-blocking. Hitherto, only toy examples were known of connectors that are wide-sense non-blocking but not strictly non-blocking, and these examples are more expensive than comparable strictly non-blocking connectors. In this paper we show for the first time how wide-sense non-blocking connectors can be less expensive than comparable strictly non- blocking connectors. In the simplest case we show that strictly non-blocking n-connectors with depth 2 must have ~2(n 2) edges, but wide-sense non-blocking n-connectors with depth 2 can have O(n 3/2 (log n) I/2) edges.

Rights Information

© 1986 Association for Computing Machinery

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

DOI

10.1145/12130.12155

Recommended Citation

Feldman, P., Friedman, J, and Pippenger, N. "Non-Blocking Networks", ACM Symp. on Theory of Computing, 18 (1986), 247-254. doi: 10.1145/12130.12155