Bit complexity of order statistics on a distributed star network (Q1116337)

We study the bit complexity of order statistics problem on an asynchronous distributed star network. We prove a lower bound of \(\Omega\) (N log(LN)) bits for the k-selection problem, and lower bounds of \(\Omega\) (N log(L-N)) bits for the problems of sorting and ranking. For each of the problems we introduce an algorithm that achieves that bound, thus showing all bounds to be optimal.