In particular in graphs where D is large, algorithm A^rand is considerably faster than the algorithm selecting only a single random element in each phase. In Section 5, we prove that no deterministic or probabilistic algorithm can be better asymptotically, i.e., A^rand is asymptotically optimal.

4. 2 Deterministic algorithm

The difficulty of deterministic iterative algorithms for k- selection lies in the selection of elements that provably allow for a reduction of the search space in each phase. Once these elements have been found, the reduced set of candidate nodes can be determined in the same way as in the randomized algorithm. Thus, the deterministic algorithm, referred to as A^det, has to compute a set of O(D) elements that partitions all elements similarly to the random set used by algorithm A^rand in each phase.

A simple idea to go about this problem is to start sending up elements from the leaves of the spanning tree, accumulating the elements from all children at the inner nodes,

and then recursively forwarding a selection of t elements to
the parent. The problem with this approach is the reduction
of all elements received from the children to the desired t
elements. If a node u receives t elements from each of its
i
c children in the spanning tree, the t elements that parti-
i
tion all c t nodes into segments of approximately equal size
i

ought to be found. However, in order to find these elements, the number of elements in each segment has to be counted starting at the leaves. Since this counting has to be repeated in each step along the path to the root, the time required to find a useful partitioning into k segments requires O(D (D + Ct) ) time, where C := max_{i∈{ 1, … ,n}} c_i. This approach suffers from several drawbacks: It takes at least O(D²) time just to find a partitioning, and the time complexity depends on the structure of the spanning tree.

Our proposed algorithm A^det solves these issues in the following manner. In any phase i, the algorithm splits the entire spanning tree into O( D) groups, each of size O(n⁽ⁱ⁾/

D). Figure 2 depicts an example tree split into 4 groups. Recursively, in each of those groups a particular node initiates the same partitioning into O( D) groups as long as the group size is larger than O( D). The goal of this recursive partitioning is to find, for each group, O( D) elements that reduce the search space by a factor of O( D). Groups of size at most O( D) can simply report all their elements to the node that initiated the grouping at this recursion level. Once such an initiating node u has received all O( D) elements from each of the O( D) groups it created, it sorts those O(D) elements, and subsequently issues a request to count the nodes in each of the O(D) intervals induced by the received elements. Assume that all the groups created by node u together contain n⁽ⁱ⁾ _u nodes in phase i. The intervals can locally be merged into O( D) intervals such that each interval contains at most O(n⁽ⁱ⁾ _u/ D) nodes. These O( D) elements are recursively sent back to the node that created the group to which node u belongs. Upon receiving the O(D) elements from its O( D) groups and counting the number of nodes in each interval, the root can initiate phase i + 1 for which it holds that n^{(i+ 1)}<n⁽ⁱ⁾/O( D).

figure 2: an example tree of diameter 12 consisting of 24 nodes is split according to algorithm A^det into 4 groups, each consisting of at most 7 nodes.

Given that the number of candidates reduces by a factor of O( D) in each phase, it follows that the number of phases is bounded by O(log n). It can be shown that each phase

D

costs O(D log_D n) time, which proves the following bound on the time complexity.

Theorem4.2. Inaconnectedgraphofdiameter D ≥ 2 consisting of n nodes, the time complexity of algorithm A^det is O(D log ² n).

D

5. lo WeR BounD

In this section, we sketch how to prove a time lower bound for generic distributed selection algorithms which shows that the time complexity of the simple randomized algorithm of Section 4. 1 for finding the element of rank k is asymptotically optimal for most values of k. Informally, we call a selection algorithm generic if it does not exploit the structure of the element space except for using the fact that there is a global order on all the elements. Formally, this means that the only access to the structure of the element space is by means of the comparison function. Equivalently, we can assume that all elements assigned to the nodes are fixed but that the ordering of elements belonging to different nodes is determined by an adversary and is initially not known to the