Selection on k-dimensional meshes with multiple broadcasting

Randomized selection algorithms on k-dimensional mesh-connected computers with multiple broadcasting are proposed in this paper. We first show that a leader can be elected in O(log N) time on any k-dimensional mesh-connected computers with multiple broadcasting of size N. We then show that we can find the p-th smallest element among a data set of size N in O((log N + k + N^1/(k(k+1))) log N) expected time using a regular N^1/k × ... × N^1/k k-dimensional mesh and in O((log N + k²N^1/(k2k)) log N) expected time using an irregular N^{(2k-1 k+1)/{k2k}} × N(2k-2 k+1)/^(k2k) × ... × N^(k+1)/(k2k) k-dimensional mesh. This leads to a selection algorithm which runs in O((log,N)²) expected time on a regular ((log N/log log N)^1/2)-dimensional mesh or on an irregular (log log N)-dimensional mesh each with N processors. To our best knowledge, this is the first polylogarithmic selection algorithm on meshes with multiple broadcasting.