Efficient Selection and Sorting Schemes for Processing Large Distributed Files in de Bruijn Networks and

K. Naik S-Y. Kuo In this paper we show the power of sampling techniques in designing efficient distributed algorithms. In particular, we show that using sampling techniques, on the hypercube and de Bruijn network, the selection can be done in such a way that the message complexity is less sensitive to the cardinality of the set (file). Our selection schemes outperform the existing approaches in terms of both message complexity and communication delay. The property that the number of messages needed and the communication delay are less sensititive to the size of the file makes our distributed selection schemes extremely attractive in such domains as very large database systems. Making use of our selection algorithms, we also show that both quicksort-based sorting scheme and enumeration sorting scheme can be developed for sorting large distributed files on the hypercube and de Bruijn networks. 1