Reduction techniques for selection in distributed files

The problem of selecting the Kth smallest element of a set of N elements distributed among d sites of a communication network is examined. A reduction technique is a distributed algorithm that transforms this problem to an equivalent one where either K or N (or both) are reduced. A collection of distributed reduction techniques is presented; the combined use of the algorithms offers new solutions for the selection problem in shout-echo networks and in a class of point-to-point networks. The communication complexity of these solutions is analyzed and shown to represent an improvement on the multiplicative constant of existing bounds for those networks