Distributed stochastic processes for generating 
random permutations 

Artur Czumaj, Przemyslawa Kanarek, Miroslaw Kutylowski, Krzysztof Lorys

Protocols of mixing items in distributed and parallel systems belong  to
the  most  important  and most frequently used in algorithmic and system
applications. In this paper we analyze various stochastic processes  for
generating almost uniformly random permutations in such systems. All our
protocols are very simple and base on performing disjoint transpositions
executed in parallel. The challenging problem of our concern is to prove
that the output configurations in our  processes  reach  almost  uniform
probability  distribution  very rapidly, i.e. in a (low) polylogarithmic
time.

For the analysis of the aforementioned  protocols  we  develop  a  novel
technique,  called  delayed  path  coupling, for proving rapid mixing of
Markov chains. Our approach is an extension of the path coupling  method
of Bubley and Dyer.

We apply  delayed  path  coupling  to  three  stochastic  processes  for
generating  random  permutations.  For  one  process,  we apply standard
(though non-trivial) coupling arguments, for the second one we construct
a  non-Markovian  coupling, and for the third one we prove the existence
of a non-Markovian coupling. To the best of our knowledge, these are the
first  non-trivial  applications  of  non-Markovian coupling for proving
rapid mixing of Markov chains.

We apply our analysis in diverse areas. We develop a simple  permutation
network  of  a polylogarithmic depth generating permutations with almost
uniform distribution. A simple EREW  PRAM  algorithm  generating  random
permutations  in  time  O(loglog  n)  with  O(n  log^O(1)  n) processors
follows. We improve technique of cryptographic defense  against  traffic
analysis  by showing that the underlying stochastic process converges in
time O(log n) (instead of polylogarithmic time) and thereby dramatically
reduce the size of a security parameter. Other applications include load
sharing in distributed systems, design of fault resistant  systems,  and
parallel  algorithms  generating  random  permutations  for  models with
restricted concurrent writes/reads.