THE BIT COMPLEXITY OF DISTRIBUTED SORTING

We study the bit complexity of the sorting problem for asynchronous di stributed systems. We show that for every network with a tree topology T, every sorting algorithm must send at least Omega(Delta(T) log(L/N) ) bits in the worst case, where {1, 2,..., L} is the set of possible i nitial values, and Delta(T) is the sum of distances from all the verti ces to a median of the tree. In addition, we present an algorithm that sends at most O (Delta(T) log((L.N)/Delta(T))) bits for such trees. T hese bounds are tight if either L = Omega(N1+epsilon) or Delta(T) = Om ega(N-2). We also present results regarding average distributions. The se results suggest that sorting is an inherently nondistributive probl em, since it requires an amount of information transfer that is equal to the concentration of all the data in a single processor, which then distributes the final results to the whole network. The importance of bit complexity-as opposed to message complexity-stems also from the f act that, in the lower bound discussion, no assumptions are made as to the nature of the algorithm.