nodes. For the lower bound, we use a simpler synchronous communication model where time is divided into rounds and in every round each node can send a message to each of its neighbors. Note that since the synchronous model is strictly more restrictive than the asynchronous model, a lower bound for the synchronous model directly carries over to the asynchronous model. We show that if in any round only one element can be transmitted over any edge, such an algorithm needs at least Ω(D log_D n) rounds to find the median with reasonable probability.

Generalizing the lower bound to finding the element of rank k for arbitrary k ∈ { 1, …, n} is straight-forward. We can assume that k ≤ n/2 because finding the element of rank k is equivalent to finding the element of rank n + 1 − k with respect to the inverse global order. We can now just inform the algorithm about the rank of all but the first 2k elements ( additional information cannot make the problem harder). The problem now reduces to finding the median of 2k elements.

Let us start with an outline of our proof strategy. The lower bound is proven in two steps. We first consider protocols between two nodes where each of the nodes starts with half of the elements. Assuming that the two nodes can send each other messages containing at most B ≥ 1 elements in each round, we show that Ω(log_B n) rounds are needed to find the median. In a second step, we obtain the desired lower bound for general graphs by means of a reduction: We construct a graph G(D) for every diameter D ≥ 3 such that every T-round median algorithm on G(D) can be turned into a T/(D − 2)-round two-party protocol in which the two nodes have to communicate D − 2 elements per message.

We therefore start by studying protocols between two nodes u and u such that u and u each have N ≥ 1 elements u₀  u₁  . . .  u_{N− 1} and u₀  u₁  . . .  u_{N− 1} respectively, where  is the global order according to which we want to find the median. We denote the sets of elements of u and u by S_u and S_u, respectively. Each message M = (S, X) between the two nodes is further assumed to contain a set S of at

most B elements and some arbitrary additional information X. Assume M is a message from u to u. In this case, X can be everything which can be computed from the results of the comparisons between all the elements u has seen so far, as well as all the additional information u has received so far. The only restriction on X is that it cannot be used to transmit information about the values of elements not in S or in one of the earlier messages. We call a protocol between u and u which only sends messages of the form M = (S, X) as described above, a generic two-party protocol.

The general idea is as follows. We define N different partitions, each assigning N of the 2N elements to u, and the other N elements to u (i.e., N different orders between the elements in S_u and S_u) in such a way that each partition results in a different median element. We choose as input one of the N partitions uniformly at random. In order to compute the median, we then have to find out which of the N partitions was chosen. We show that in each communication round, the probability for reducing the number of possible partitions by more than a factor of lB is exponentially small in l.

For simplicity, assume that N = 2^l is a power of 2. Let X₀, …, X_{l− 1} ~ Bernoulli(1/2) be l independent Bernoulli variables, i.e., all X_i take values 0 or 1 with equal probability. The partition of the 2N elements among u and u is determined by the values of X₀, …, X_{l− 1}. If X_{l− 1} = 0, the N/2 smallest of the 2N elements are assigned to u and the N/2 largest elements are assigned to u. If X_{l− 1} = 1, it is the other way round. In the same way, the value of X_{l− 2} determines the assignment of the smallest and largest N/4 of the remaining elements: If X_{l− 2} =0, u gets the elements with ranks N/2 + 1,…, 3N/4 and u gets the elements with ranks 5N/4 + 1, …, 3N/2 among all 2N elements. Again, the remaining elements are recursively assigned analogously depending on the values of X_{l− 3}, …, X₀ until only the two elements with ranks N and N + 1 (i.e., the two median elements) remain. The element with rank N is assigned to u and the element with rank N + 1 is assigned to u. Figure 3 illustrates the described process.

figure 3: the 2N elements minus the two medians are assigned to u and u according to l = log n independent Bernoulli variables X , …, X . one
0 l− 1
of the two medians is assigned to u and the other to u. in order to find the medians, u and u must compute the values of X , …, X .