Fast communication is one of the fundamental problems of parallel computing on a fixed-connection network architecture, especially if physical limitations are imposed that the networks be wire- (edge-)sparse, have constant (or logarithmically growing) valence, and that each processor only has access to local information. The second author’s scheme [1] has the added advantage that the local algorithm is uniform for all processors and can be adapted to nonsynchronous networks. This scheme makes random choices to push information to intermediate nodes before they reach their final destination. Nevertheless, it is guaranteed to deliver information packets at their destinations within linear time with exponentially small probability of error.

The research of the paper exploits this algorithm together with two new procedures--SF (for key Splitter Finding) and SDR (Splitter-Directed Routing)--to achieve (essentially optimal) O(log N) sorting on cube-connected-cycle type networks, still with an exponentially low probability of error in a single run. Similar previous results [2] achieve optimal lower bounds on an expander network, but the authors also observe that their algorithm has constants “enormously” smaller (which, presumably, makes it more implementable) and uses a more versatile architecture.