Non-blocking networks

Publisher Website
Google Scholar
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 con- nectors 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.

This publication has 0 references indexed in Scilit: