Sorting from independently chosen comparisons

user_1114253 0
Viewed 47

I want to sort a list of n items from pairwise comparisons. Each round, I receive k comparisons, one each from k different "arbiters".

The arbiters cannot coordinate, and must choose their comparisons independently from myself and each other. How should they choose their comparisons so that I can sort the list of items in as few rounds as possible?

A naive solution is that each arbiter independently runs quicksort, sending over the corresponding comparisons they make. Ultimately, I'd just be waiting for one arbiter to finish sorting, so this would take O(n*log(n)) rounds for me to sort the list, and I literally receive no benefit from having k arbiter over just a single arbiter.

Another naive solution is each arbiter independently sends over random comparisons. This would result in a coupon collector problem, and would taken on average O(n^2*log(n)/k) rounds for me to get the right comparisons to sort the list. But unless k is in ω(n), this run-time isn't better than O(n*log(n)).

Is there a better solution? Maybe one that uses O(n*log(n)/k) rounds? (i.e. double the arbiters = half the rounds needed)

To be more concrete about the independence of arbiters: ideally, the arbiters would use symmetric randomized strategies. If that's not possible, though, then I'll allow the arbiters to have a strategy meeting one time only at the start.

Also, arbiters have to send exactly the comparisons they make. E.g. an arbiter cannot just sort the entire list themselves, and then send only the comparisons (arr[i] < arr[i+1]) for i=0 to n-2. They have to send each comparison they make as they make it.

parallel-processing distributed time-complexity sorting algorithm
2 Answers

I think I have a solution. It's totally symmetric with no coordination.

Each arbiter runs the following algorithm to choose their comparisons.

First, they consider evenly dividing n into k "sections" (e.g. section 1 is from 1 to n/k, section 2 is from n/k+1 to 2n/k, etc.). Then, they randomly choose one of k sections to focus on. Next, they use quickselect to get all the elements that will end up in their section (which takes O(n) comparisons). Finally, they fully sort their section (which takes O(n*log(n)/k) comparisons). After that, they randomly choose another section and repeat.

To get all k sections sorted, it's a coupon collector problem, and takes k*log(k) tries, which, when distributed over k arbiters, will only take log(k) tries.

So the final number of rounds of this approach will be O(n*log(k) + n*log(n)*log(k)/k) = O(n*log(n)*log(k)/k), which gives you an improvement factor of log(k)/k. This can be upgraded to 1/k if the arbiters are allowed to choose at the start which sections they're in charge of.

user_11142530
  1. If they can coordinate their own numbers.
    Here's an idea. First, partition the array in k parts as for quicksort. First have everybody partition the entire array in 2 synchronously. Then let the first half of the arbiters partition the first half of the array while the second half of the arbiters partition the second half of the array, and so on. This takes no more than 2n rounds. Next, let arbiter number i sort the partition number i. This takes (n/k) log (n/k) rounds.
  2. If they cannot coordinate their own numbers.
    The same idea but it takes longer. You still have them partition the array in k parts, only now they have to do it all the way down synchronously, so you don't benefit from having k arbiters at this stage. This takes n log k rounds. Then let each arbiter sort each partition in randomly chosen order. I'm too lazy to calculate the expected number of rounds here. Off the top of my head, you will need about e (n/k) log (n/k) rounds, but don't quote me.
  3. Another way if they cannot coordinate their own numbers.
    Almost the same as above, but have each arbiter partition in a random order (first partition in half, then randomly choose which half to partition further etc). Sort as soon as there is a partition of size n/k, then randomly select what to partition next. This is harder to analyse than the above but should be faster.
user_7758060
Related