Tight bounds for distributed selection
Fabian Kühn, Thomas Locher, Rogert Wattenhofer · 2007
We revisit the problem of distributed k-selection where, given a general connected graph of diameter D consisting of n nodes in which each node holds a numeric element, the goal is to determine the kth smallest of these elements. In our model, there is no imposed relation between the magnitude of the stored elements and the number of nodes in the graph. We propose a randomized algorithm whose time complexity is O(DlogD n) with high probability. Additionally, a deterministic algorithm with a worst-case time complexity of O(Dlog2 D n) is presented which considerably improves the best known bound for deterministic algorithms. Moreover, we prove a lower bound of Ω(D logDn) for any randomized or deterministic algorithm, implying that the randomized algorithm is asymptotically optimal.