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
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.