# Algorithms / heuristics for a distributed sorting problem

The setting:

• There's a cluster of $$k$$ computers (= nodes). For simplicity, assume their hardware is identical.
• The network topology can be complicated, but let's simplify and assume it's a clique with fixed bandwidth B bits/time unit between each pair of nodes.
• Each node has its own limited amount of memory, $$M$$.
• There's a multi-set of $$n$$ integers (of fixed width $$w$$ bits), and each node has some of these integers.
• The number of elements is not uniform among the nodes.
• There are more elements to be sorted than there are cluster machines, i.e. $$k < n$$, and you may assume $$k \ll n$$ if you like.
• Each node has "scratch space" which is at least $$s$$ times the average space taken up by data on a node (i.e. at least $$snw/k$$). So we have $$\Theta(n)$$ extra space to use, but it's distributed among the nodes.

I'm interested in algorithms for sorting the data. The desire is to minimize the overall time, with network traffic taking up time according to the stated bandwidth.

Notes:

• I haven't defined exactly what each node can do in a given time unit, and that's intentional. Assume the nodes are abstract RAM machines with one operation per time unit, or choose a different model if you like. The real life motivation involves actual full-fledged physical computers in a cluster.
• It does not matter which node in the cluster ends up with which elements, provided that the nodes' elements can be concatenated to form a sorted sequence (and each node holds the positions of the elements it holds in this concatenation).
• It's useful, though not necessary, for each node to know which other node ends up with which elements.
• Randomized algorithms are acceptable, but only Las Vegas rather than Monte Carlo, i.e. the result must always be correct.
• Assume there are no node faults and no communication faults.
• Node clocks are sort-of-synchronized, but the algorithm shouldn't do anything funny and cute using perfect synchronization.
• A node does not and cannot have more than $$n_\text{node-max}$$ elements - both before and after the sort. i.e. the element distribution skew is bounded.
• Algorithms in which the inter-node activity parallelizes well are desirable.
• Important: I'm interested two variants of the sorting:

1. Data becomes sorted among the nodes, but not necessarily within the nodes, i.e. for the appropriate order of nodes and for $$x \neq y$$ in nodes $$v_i$$ and $$v_j$$ respectively - $$x < y$$ implies $$i \leq j$$ (but weak inequality doesn't apply, because two consecutive nodes can have identical values).
(obviously, if we reach this state, the rest of the data can be sorted in $$\tilde{O}(M/sw)$$ by each node performing its own local sort.)
2. Data becomes completely sorted - within and between nodes.

Finally, if there are similar, related problems you know of but not a solution to mine, leave a comment or speculate in an answer on how they might be adapted.