Derandomizing algorithms for routing and sorting on meshes

Abstract

We describe a new technique that can be used to derandomize a number of randomized algorithms for routing and sorting on meshes. We demonstrate the power of this technique by deriving improved deterministic algorithms for a variety of routing and sorting problems. Our main results are an optimal algorithm for k-k routing on multi-dimensional meshes, a permutation routing algorithm with running time 2n+o(n) and queue size 5, and an optimal algorithm for 1-1 sorting. 1 Introduction One of the main problems in the simulation of idealistic parallel computers by realistic ones is the problem of message routing through the sparse network of links connecting a set of processing units (PUs) among each other. In this paper, we consider the case of the n \\Theta n mesh, in which n 2 PUs are connected by a regular twodimensional grid of bidirectional communication links. There may also be additional wrap-around connections between the two PUs at opposite ends of each row and each column of t...