Title :
Distributed Sorting
Author :
Rotem, Doron ; Santoro, Nicola ; Sidney, Jeffrey B.
Author_Institution :
Department of Computer Science, University of Waterloo, Waterloo, Ont., Canada.
fDate :
4/1/1985 12:00:00 AM
Abstract :
The problem of sorting a file distributed over a number of sites of a communication network is examined. Two versions of this problem are investigated; distributed solution algorithms are presented; and their communication complexity analyzed both in the worst and in the average case. The worst case bounds are shown to be sharp, with respect to order of magnitude, for large files.
Keywords :
Algorithm design and analysis; Communication networks; Complexity theory; Computer science; Councils; Distributed computing; Sorting; Water storage; Distributed algorithms; message complexity; minimum spanning tree; selection; sorting;
Journal_Title :
Computers, IEEE Transactions on
DOI :
10.1109/TC.1985.5009389
