Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

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 $p \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?

share|improve this question
    
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/… –  Geoffrey Irving Dec 30 '12 at 5:39
    
Totally cool. I think it's an interesting question. –  Geoff Oxberry Dec 30 '12 at 7:49
1  
One fun bit is that the inverse of the permutation gives which process owns a given index. –  Geoffrey Irving Dec 30 '12 at 8:36
add comment

1 Answer

up vote 4 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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