Chapter 4 Distributed Sorting

“Indeed, I believe that virtually every important aspect of programming arises somewhere in the context of sorting [and searching]!” – Donald E. Knuth, The Art of Computer Programming In this chapter we study a classic problem in computer science—sorting— from a distributed computing perspective. In contrast to an orthodox single-processor sorting algorithm, no node has access to all data, instead the to-be-sorted values are distributed. Distributed sorting then boils down to: Definition 4.1 (Sorting). We choose a graph with n nodes v1,..., vn. Initially each node stores a value. After applying a sorting algorithm, node vk stores the kth smallest value. Remarks: • What if we route all values to the same central node v, let v sort the values locally, and then route them to the correct destinations?! According to the message passing model studied in the first few chapters this is perfectly legal. With a star topology sorting finishes in O(1) time! Definition 4.2 (Node Contention). In each step of a synchronous algorithm, each node can only send and receive O(1) messages containing O(1) values, no matter how many neighbors the node has. Remarks: • Using Definition 4.2 sorting on a star graph takes linear time