# zbMATH — the first resource for mathematics

Fast generation of random permutations via networks simulation. (English) Zbl 0896.68071
Summary: We consider the problem of generating random permutations with uniform distribution. That is, we require that for an arbitrary permutation $$\pi$$ of $$n$$ elements, with probability $$1/n!$$ the machine halts with the $$i$$th output cell containing $$\pi(i)$$, for $$1\leq i\leq n$$. We study this problem on two models of parallel computations: the CREW PRAM and the EREW PRAM.
The main result of the paper is an algorithm for generating random permutations that runs in $$O(\log\log n)$$ time and uses $$O(n^{1+o(1)})$$ processors on the CREW PRAM. This is the first $$o(\log n)$$-time CREW PRAM algorithm for this problem.
On the EREW PRAM we present a simple algorithm that generates a random permutation in time $$O(\log n)$$ using $$n$$ processors and $$O(n)$$ space. This algorithm outperforms each of the previously known algorithms for the exclusive write PRAMs.
The common and novel feature of both our algorithms is first to design a suitable random switching network generating a permutation and then to simulate this network on the PRAM model in a fast way.

##### MSC:
 68W15 Distributed algorithms
##### Keywords:
random permutations; CREW PRAM; EREW PRAM
Full Text: