It's easy to come up with a simple distributed algorithms for finding the maximum element in a set (totally ordered): Divide and conquer.
There are a few publications that present algorithms for distributed maximum-finding. The challenge is to pass the fewest messages between nodes.
Does anyone know of algorithms that tackle the same problem for the distributed "n-largest-finding" problem?
A naive solution is a repeated application of a distributed maximum-finding algorithm by successively slicing off the maximums. Another naive solution is to use a distributed sort. These two are probably not even that bad in the extreme cases (very small n, very large n). But how about finding the 10% largest elements (the top decile)?
For reference: There's a question on SO, CUDA: Finding the N largest values of a sparse array, which leads to just using a sort.
