Efficient distributed selection with bounded messages

We consider the problem of selecting the Kth smallest element of a set distributed among the sites of a communication network when the size of messages is bounded; that is, each message is a packet which contains at most c bits, where c/spl ges/1 is a constant. A general selection algorithm using packets is presented and its packet complexity is analyzed. Its complexity is shown to be a significant improvement for a large range of packet sizes over the existing bounds. The proposed technique is then instanciated for specific classes of network topologies; the resulting bounds either match or improve the ones of existing solutions for a large range of values of the packet size. Furthermore, it is bit optimal in star networks.