Optimal Distributed Algorithms for Sorting and Ranking
We study the problems of sorting and ranking n processors that have initial values - not necessarily distinct - in a distrubuted 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 me...
| Main Author: | |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149071 |
| _version_ | 1826192478291623936 |
|---|---|
| author | Zaks, Shmuel |
| author_facet | Zaks, Shmuel |
| author_sort | Zaks, Shmuel |
| collection | MIT |
| description | We study the problems of sorting and ranking n processors that have initial values - not necessarily distinct - in a distrubuted 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 1/2n^2 + O(n) such messages. The algorithm is them extended to perform sorting, using in the worst case at most 3/4n^2 + 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 are discussed. Assuming that the initial values, identities and ranks can only be compared within themselves, lower bounds of 1/2n^2 and 3/4n^2 messages are proved for a worst case execution of any algorithm to solve the ranking and sorting problems, correspondingly. |
| first_indexed | 2024-09-23T09:15:46Z |
| id | mit-1721.1/149071 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T09:15:46Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1490712023-03-30T04:12:43Z Optimal Distributed Algorithms for Sorting and Ranking Zaks, Shmuel We study the problems of sorting and ranking n processors that have initial values - not necessarily distinct - in a distrubuted 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 1/2n^2 + O(n) such messages. The algorithm is them extended to perform sorting, using in the worst case at most 3/4n^2 + 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 are discussed. Assuming that the initial values, identities and ranks can only be compared within themselves, lower bounds of 1/2n^2 and 3/4n^2 messages are proved for a worst case execution of any algorithm to solve the ranking and sorting problems, correspondingly. 2023-03-29T14:24:35Z 2023-03-29T14:24:35Z 1984-05 https://hdl.handle.net/1721.1/149071 14402468 MIT-LCS-TM-261 application/pdf |
| spellingShingle | Zaks, Shmuel Optimal Distributed Algorithms for Sorting and Ranking |
| title | Optimal Distributed Algorithms for Sorting and Ranking |
| title_full | Optimal Distributed Algorithms for Sorting and Ranking |
| title_fullStr | Optimal Distributed Algorithms for Sorting and Ranking |
| title_full_unstemmed | Optimal Distributed Algorithms for Sorting and Ranking |
| title_short | Optimal Distributed Algorithms for Sorting and Ranking |
| title_sort | optimal distributed algorithms for sorting and ranking |
| url | https://hdl.handle.net/1721.1/149071 |
| work_keys_str_mv | AT zaksshmuel optimaldistributedalgorithmsforsortingandranking |