Power and Limitations of Optical Reconfigurable Arrays

The mesh with optical reconfigurable buses is one of the strongest interconnection networks one can think of. There is a constant-time randomized selection algorithm. In this paper, a deterministic selection algorithm is given that runs in $\go{(\log\log N)^2}$ time. It was known that $h$-relations can be routed randomizedly in $\go{h}$ time, here we show that the same can be achieved with a deterministic algorithm. The sorting problem is analyzed in detail, and a new faster algorithm is presented