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.
© 1986 Association for Computing Machinery
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