Fast generation of random permutations via network simulation,
                   Artur Czumaj, Przemyslawa Kanarek, 
                   Miroslaw Kutylowski, Krzysztof Lorys,

We consider the classical problem of generating random permutations with
the  uniform  distribution.  That  is,  we require that for an arbitrary
permutation pi of n elements, with probability 1/n!  the  machine  halts
with  the  ith  output  cell containing pi(i), for 1 =< i =< 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(loglog  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 matches the running time and the number of processors used  of
the  best  previously  known  algorithms for the CREW PRAM, and performs
better as far as the memory usage is considered.

The common and novel feature of both our algorithms is to design first a
suitable  random  network  generating a permutation and then to simulate
this network on the PRAM model in a fast way.