Efficient selection and sorting schemes using coteries for processing large distributed files

In this paper, we develop efficient selection and sorting schemes for processing large files distributed over a network. The efficiencies of the schemes are expressed in terms of message count and communication delay. The schemes are developed using the concept of coteries which is a class of communication structures widely used in the development of some classical distributed algorithms, namely mutual exclusion, multiway rendezvous, etc. The development of the schemes is carried out as follows. First, we develop a ranking scheme. Second, using the ranking scheme, we develop a restricted version of sorting, where each node of the network contains exactly one key, and the sorting leads to the ith node holding the ith key of the sorted list. Third, using this restricted sorting, a selection scheme is developed. Given n keys evenly distributed among p nodes, selection of the kth key means identifying the value of the key. Finally, using the idea of selection, we sort the n keys distributed among p nodes. Both the ranking and the restricted sorting steps need O(p p) messages and suffer a two-round communication delay. The selection step needs O(p^3/2 log n) messages with communication delay of O(τ log p), where τ is the maximum of the times taken by a message to be sent to all the members of a quorum. The sorting scheme needs O(n) messages and its communication delay is O(τp/n). Both of these complexities are optimal provided n is polynomial in p and n = Ω(p^5/2 log n).