Optimal Distributed Algorithms for Sorting and Ranking
Author:
- 1 April 1985
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-34 (4) , 376-379
Abstract
We study the problems of sorting and ranking n processors that have initial values (not necessarily distinct) in a distributed system. Sorting means that the initial values have to move around in the network and be assigned to the processors according to their distinct identities, while ranking means that the numbers 1, 2,..., n have to be assigned to the processors according to their initial values; ties between initial values can be broken in any chosen way. Assuming a tree network, and assuming that a message can contain an initial value, an identity, or a rank, we present an algorithm for the ranking problem that uses, in the worst case, at most n2/2+O(n) such messages. The algorithm is then extended to perform sorting, using in the worst case at most 3n2/4+O(n) messages. Both algorithms are using a total of O(n) space. The algorithms are extended to general networks. The expected behavior of these algorithms for three classes of trees is discussed. Assuming that the initial values, identities, and ranks can be compared only within themselves, lower bounds of n2/2 and 3n2/4 messages are proved for a worst case execution of any algorithm to solve the ranking and sorting problems, respectively.Keywords
This publication has 8 references indexed in Scilit:
- Distributed SortingIEEE Transactions on Computers, 1985
- Distributed algorithms for finding centers and medians in networksACM Transactions on Programming Languages and Systems, 1984
- The complexity of sorting on distributed systemsInformation and Control, 1984
- A Distributed Algorithm for Minimum-Weight Spanning TreesACM Transactions on Programming Languages and Systems, 1983
- Symmetry breaking in distributive networks1981
- Applied tree enumerations1981
- The distance between points in random treesJournal of Combinatorial Theory, 1970
- The enumeration of rooted trees by total heightJournal of the Australian Mathematical Society, 1969