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.