2015/11/02 by Piotr Berman, Berman, Piotr, Junichiro Fukuyama +1
Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Distributed systems and fault tolerance #F.2.2 #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1511.00715
openalex publication_date 2015/11/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 kth 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ós and Szemeré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.