Parallel algorithms for generating random permutations on a shared memory machine
Richard J Anderson · 1990
In this paper we consider the problem of generating random permutations on small parallel machines.The machines that we have in mind are shared memory machines with a constant number of processors such as the Sequent Symmetry.We describe a parallel implementation of the "shuffling" algorithm for generating a random permutation.If the hardware operates in a fair manner, this algorithm generates a fully random permutation.However, if the machine resolves contention in a malicious manner, then the algorithm does not generate permutations uniformly.We give almost tight bounds on the degree that an adversary can reduce the randomness.We also discuss the cost of locking data in the algorithm and present a method of generating random permutations with substantially reduced locking cost.