RANDOMIZED SORTING ON THE POPS NETWORK

TL;DRAbstract

Partitioned Optical Passive Stars (POPS) network has been presented recently as a desirable model of parallel computation. Several papers have been published that address fundamental problems on this architecture. The algorithms presented in this paper are valid for POPS(d,g) where d>g and use randomization. We present an algorithm that solves the problem of sparse enumeration sorting of d ∊ keys in [Formula: see text] time and hence performs better than previous algorithms. We also present algorithms that allow us to do stable sorting of integers in the range [1, log n] and [Formula: see text] in [Formula: see text] time. When g=n ∊ , for any constant 0<∊<½ this allows us to do sorting of integers in the range [1,n] in [Formula: see text] time. We finally use these algorithms to solve the problem of multiple binary search in the case where we have d ∊ keys in [Formula: see text] time and in the case where we have integer keys in the range [1,n] in [Formula: see text] time, wh

Chat with Paper

AI Agents for this Paper