  We consider the selection problem on a completely connected network of $n$
processors with no shared memory. Each processor initially holds a given
numeric item of $b$ bits allowed to send a message of $\max ( b, \lg n )$ bits
to another processor at a time. On such a communication network ${\cal G}$, we
show that the $k$th smallest of the $n$ inputs can be detected in $O ( \log n
)$ time with $O ( n \log \log n )$ messages. The possibility of such a parallel
algorithm for this distributed $k$-selection problem has been unknown despite
the intensive investigation on many variations of the selection problem carried
out since 1970s. The main trick of our algorithm is to simulate the comparisons
and swaps performed by the AKS sorting network, the $n$-input sorting network
of logarithmic depth discovered by Ajtai, Koml{\'o}s and Szemer{\'e}di in 1983.
We also show the universal time lower bound $\lg n$ for many basic data
aggregation problems on ${\cal G}$, confirming the asymptotic time optimality
of our parallel algorithm.
