6
$\begingroup$

I have a large number of parallel processes and a large integer $n$, and want to randomly partition the integers $[0,n)$ among the processes with only $O(1)$ communication.

One nice way to do this would to generate a pseudorandom permutation $\pi \in S_n$ represented as a small function, so that only the random key/seed need be exchanged. Is there a good way to do this?

$\endgroup$
3
  • $\begingroup$ I'm about to answer this myself. I was about to answer it on stackoverflow, but it was closed as "not a question": stackoverflow.com/questions/14077953/… $\endgroup$ Dec 30 '12 at 5:39
  • 1
    $\begingroup$ Totally cool. I think it's an interesting question. $\endgroup$ Dec 30 '12 at 7:49
  • 1
    $\begingroup$ One fun bit is that the inverse of the permutation gives which process owns a given index. $\endgroup$ Dec 30 '12 at 8:36
6
$\begingroup$

Pick $2^k$ slightly larger than $n$, generate a block cypher $f \in S_{2^k}$ operating on $k$ bit blocks, and construct a permutation on $[0,n)$ by walking along cycles of $f$ until we get back in the desired range. Specifically, given $x < n$ we set $$g(x) = f^p(x) = f(f(f(...x...)))$$ where $p$ is the least positive integer s.t. $f^p(x) < n$.

If $2^k = O(n)$, and the block cypher is good, the walk takes $O(1)$ expected time. Note that $p$ is necessarily finite, since eventually we will walk back around the cycle and find $f^p(x) = x$.

For more details, see

  1. Black and Rogaway, Ciphers with Arbitrary Finite Domains, 2001.
  2. http://blog.notdot.net/2007/9/Damn-Cool-Algorithms-Part-2-Secure-permutations-with-block-ciphers

Here is an example implementation using a truncated TEA block cypher as described in (2):

https://github.com/otherlab/core/blob/f09fbd19dbaa7b9033eb0888594273a6a3d592a5/random/permute.cpp

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.