Consider the two elements u_a* and u_b* with ranks N and N + 1, respectively, and let a * and b* be the ranks of the elements N and N + 1 within the sets S_u and S_u. We consider the median problem to be solved as soon as either u knows a* or u knows b*. The elements are partitioned in such a way that the random variables X directly determine the base- 2

i
representations of a* and b*. If X₀ = 0, the most significant
bit of the bit representation of a* is 1, whereas the most
significant bit of the bit representation of b* is 0. If X₀ = 1,
the most significant bit of a* is 0 and the most significant
bit of b* is 1. The other bits of the base- 2 representations of
a* and b* are determined analogously: If X_i = 0, the (i + 1)
st-most significant bit of a* is 1 and the (i + 1)st-most sig-
nificant bit of b* is 0 and vice versa if X_i = 1. Consider two
arbitrary elements u_a ∈ S_u and u_b ∈ S_u with ranks a and b
within the two sets S_u and S_u, respectively. The outcome of
the comparison of u_a and u_b (i.e., whether u_a  u_b or u_b  u_a)
is determined by the first variable X that is equal to the cor-
i
responding bit in the base- 2 representation of u_a or differ-
ent from the corresponding bit in the base- 2 representation
of u_b, whatever occurs first. If X_i = 0, we have that u_a  u_b,
otherwise u_b  u_a.
Clearly, u and u can only learn about a* and b* from com-
parisons between their own elements and elements they
have received from the other node and from additional in-
formation that the nodes sent to each other. Consider a ge-
neric two-party algorithm A that computes the median. As-
sume that after a certain time of the execution of A, u ,…,
a1
u_ar are the elements that u has sent to u and u_b1, …, u_bs are the
elements that u has sent to u. Let î be the largest index such
that there is an element u for which the first î bits are differ-
bj
ent from the corresponding variable X or such that there is
i
an element u_bj for which the first î bits are equal to the cor-
responding variable X_i. By the above observation, any com-
parison between an element in S_u and an element that u has
sent to u and any comparison between an element in S_u and
an element that u has sent to u is determined by the values of
X₀, …, X_{î+ 1}. Intuitively, u and u cannot have any information
about the values of X_{î+ 2}, …, X_{l− 1}. Thus, u and u have to guess
the remaining bits by sending each other the right elements.
It can be shown that the probability for guessing at least x
bits correctly in a single round is at most 2B/2^x. The number
of newly learned bits in each round can be upper bounded
by independent random variables. Using a Chernoff-type
argument, one can then show that log_8B(N)/c rounds are
needed to learn all l bits X₀, …, X_{l− 1} with probability at least
1

–

1

/

c

1 – 1/N ², implying the following theorem.

Theorem 5. 1. Every, possibly randomized, generic two-party protocol to find the median needs at least Ω(log_2B N) rounds in expectation and with probability at least 1 − 1/N^d for every constant d < 1/2.

Based on the lower bound for two-party protocols, we can now prove a lower bound for generic selection algorithms on general graphs. In the following, we assume that every node of a graph with n nodes starts with one element and that we have to find the k^th smallest of all n elements. In every round, every node can send one element to each of its neighbors.

For every n ≥ D ≥ 3, we construct a graph G(D) with n nodes and diameter D such that we can reduce the problem of finding the median by a two-party protocol to the problem of finding the element of rank k in G(D).

We first describe a lower bound of Ω(D log_D n) for finding the median and then generalize to finding the element of an arbitrary rank k. For simplicity, assume that n − D is an odd number. Let N = (n − D + 1)/2. We consider the graph G(D) defined as follows: The graph G(D) consists of two nodes u and u that are connected by a path of length D − 2 (i.e., it contains D − 1 nodes). In addition,

there are nodes u₁, …, u_N and u₁, …, u_N such that u_i is con-
nected to u and u_i is connected to u for all i ∈ { 1, …, N}.
We can certainly assume that n = w (D) because Ω(D) is a
trivial lower bound (even finding the minimum element
requires Ω(D) rounds). We can therefore assume that only
the leaf nodes u and u for i ∈ { 1, …, N} hold an element
ii
and that we need to find the median of these 2N elements.
We can simply assign dummy elements to all other nodes
such that the global median is equal to the median of the
leaf elements. Since only the leaves start with an element,
we can assume that in the first round, all leaves u_i send
their element to u and all leaves u_i send their element to
u, as this is the only possible useful communication in the
first round. By this, the problem reduces to finding the
k^th smallest element of 2N elements on a path of length
D − 2 if initially each of the two end nodes u and u of the
path holds N elements. Note that the leaf nodes of G(D) do
not need to further participate in a distributed selection
protocol since u and u know everything their respective
leaves know and can locally simulate all actions of their
leaf nodes.
Assume that we are given an algorithm A that finds the
median on G(D) in time T + 1. We sketch how to construct a
two-party protocol A' that sends at most D − 2 elements per
message and finds the median in time [ T/(D − 2)], The Ω(log
D
N) lower bound for such an algorithm A' then implies that
T = Ω(D log N). Because information needs at least D − 2 to
D
travel from u to u and vice versa, everything u and u can com-
pute in round t (i.e., after receiving the message from round
t − 1) is a function of their own elements and the content of
the messages of the other node up to round t − (D − 2). For ex-
ample, u’s messages of the first D − 2 rounds only depend on
S , the messages of rounds D − 1, …, 2(D − 2) can be computed
u
from S and u’s messages in the first D − 2 rounds, and so
u
on. To obtain a two-party protocol A' from A, we can proceed
as follows. In the first round of A', u and u send their mes-
sages of the first D − 2 rounds of A to each other. Now, u and
u can both locally simulate all communication of the first
D − 2 rounds of A. This allows to compute the messages of
the next D − 2 rounds of A. In general, in round r of the two-
party protocol A', u and u can send each other their messages
of rounds (r − 1) (D − 2) + 1, …, r (D − 2) of A and can afterwards
locally simulate the respective rounds of A. The time com-
plexity of A' then becomes [T/(D − 2)].

Theorem 5. 2. For every n ≥ D ≥ 3, there is a graph G(D) with n nodes and diameter D such that every, possibly randomized, generic algorithm to find the k^th smallest element requires