本論文では, BSP(Bulk-Synchronous Parallel)モデル上で 選択問題を解く並列アルゴリズムを提案する. BSPモデルは Valiant によって近年提案された非同期式並列計算モデルである. このモデルでは,具体的なネットワーク構造やメッセージ配送の遅延などが 同期周期, 通信路帯域幅を表す パラメタ L,g によりそれぞれ抽象化されている. このため, 並列計算機のアーキテクチャに依存せずに アルゴリズムの設計及び解析を行なうことができるので, 非同期式並列処理のための標準的な並列計算モデルとしての 役割が期待されている.
本論文では, データ数 n の選択問題に対し,
内部計算時間 O(n/p+L((log n)/(log(n/(p log n))+log p loglog n)),
通信時間 O(gn/p+L((log n)/(log(n/(p log n))+log p loglog n))
のpプロセッサ並列アルゴリズムを提案する.
このアルゴリズムは, p≦n/(L log n loglog n),
かつ g=O(1) のとき時間計算量とプロセッサ数の積
が O(n) となり, 最適な逐次アルゴリズムの時間計算量とオーダー的に等しい
ので, 最適加速な並列アルゴリズムである.