I recently stumbled across some other ways that random number generation can go wrong.
Suppose you want reproducible results from a seed, along with parallelism. Algorithmic random number generators are usually mutable and generate a sequence of results, limiting parallelism. Rather than a sequence, you want something tree-shaped where you can create an independent random stream for each child task. In higher-level API's, a jump or split operator can be useful.
Counter-based random number generators [1] seem pretty useful in that context. An immutable random number generator works like a hash algorithm that maps each input to an output that's difficult to predict. The problem with this is being careful to avoid using the same input twice. You can think of it as allocating random numbers from a very large address space in a reproducible way. How do you partition the address space, predictably, so that every address is used at most once, and nobody runs out?
Giving each child a unique ID and generating a stream from that is one way. If the tree is deeper, you'll want a unique seed for each path.
When a mutable random number generator is copied to a child task (or maybe just to an iterator), the same random numbers might be generated in two places. Avoiding this is the sort of thing that Rust's borrow checker can prevent - borrowing is okay, but you want to prevent multiple concurrent ownership.
When a mutable random number generator is copied to a child task
When you make a child task, the parent adds one to the internal state of the random number generator and advances the random sequence by one. The child adds two to the internal state and advances the random sequence by one.
Now you can make any arbitrary tree of tasks, and those tasks each get their own random stream, there is no shared-between-task state or locking needed, and the whole thing is reproducible, even if parent and child tasks are scheduled arbitrarily. fork-ing and use of random numbers can be arbitrarily intermingled.
Makes sense. Do you have any particular implementations in mind that work this way?
I think this depends on the random number generator. For a counter-based RNG, the "internal state" is just a counter, so adding 1 or 2 would result in reusing random numbers in different streams.
The complexity is because it is not a cryptographic pseudorandom generator.
If you have something cryptographic, than any basic operation on the internal state (ie. Increment by one) is enough to totally change the output stream in a way and outsider cannot predict.
You have to think about how your operations interact with other operations you might also do on the random state. Like what if you add one to the state, but someone else subtracts one from the state back to where you started, ooops! Or what if you create a new rng2 by adding one to the state of rng1. Then later you create rng3 by adding one to the state of rng1. Now rng2==rng3. Oops!
That's why I like the orignal idea you described of adding 1 and 2 and advancing each rng. This ensures that both streams are irreversibly altered which should make it very hard to accidentally misuse.
This seems like an area where a mutable API beats an immutable API. It's very easy to accidentally reuse old states when doing functional programming. On the other hand, if you need a way to serialize the RNG, (to send it to another task, perhaps) then the risk of reusing states comes back again.
The counter-based RNG I was looking at is an immutable API. It makes it easy to initialize generators in separate tasks by feeding each one a unique ID, but figuring out how to do a split operation is harder. Conceptually, the way to go is to multiply the key by 2 and add either 0 or 1 for each branch, to give them unique IDs. (This is called a pedigree.) However, for unbalanced trees, you will run out of bits. Figuring out how to do deal with that seems tricky?
The LXM generator paper (non-crypto) looks like good reading:
They initialize the new child with the next random values of the parent. There is an extra parameter that they use to add more input bits, to reduce the probability of overlap.
Another fun one for reproducibility -- rounding. It can happen when compiled for multiple architectures, compiling a second time with different optimizations, .... Things like normal random numbers are generated through _some_ kind of rejection sampling, and crossing that threshold from different rounding behavior will give you a wildly different result. Even if all your application code is tolerant of small perturbations, the result isn't reasonably reproducible.
Another way things go wrong with the prng tree idea (assuming the implementation is correct and you actually have independent streams) is race conditions in other parts of your code. E.g., say you have two workers reading a queue and using fancy tree-based randomness. You don't have "race" conditions (data races) in safe Rust without a compiler bug, but the language doesn't define which worker will read which item from the queue. You wind up using a different part of the stream for different inputs.
With the counter-based RNG approach, apparently one idea is that you uniquely identify child nodes in your tree somehow. That is, each work unit is a node with a unique ID that's deterministically assigned and has nothing to do with random number generation at all. Then you use that to pick the random stream.
An API that uses split or jump seems a little easier to screw up.
Comments
I recently stumbled across some other ways that random number generation can go wrong.
Suppose you want reproducible results from a seed, along with parallelism. Algorithmic random number generators are usually mutable and generate a sequence of results, limiting parallelism. Rather than a sequence, you want something tree-shaped where you can create an independent random stream for each child task. In higher-level API's, a jump or split operator can be useful.
Counter-based random number generators [1] seem pretty useful in that context. An immutable random number generator works like a hash algorithm that maps each input to an output that's difficult to predict. The problem with this is being careful to avoid using the same input twice. You can think of it as allocating random numbers from a very large address space in a reproducible way. How do you partition the address space, predictably, so that every address is used at most once, and nobody runs out?
Giving each child a unique ID and generating a stream from that is one way. If the tree is deeper, you'll want a unique seed for each path.
When a mutable random number generator is copied to a child task (or maybe just to an iterator), the same random numbers might be generated in two places. Avoiding this is the sort of thing that Rust's borrow checker can prevent - borrowing is okay, but you want to prevent multiple concurrent ownership.
[1] https://en.wikipedia.org/wiki/Counter-based_random_number_ge...
When you make a child task, the parent adds one to the internal state of the random number generator and advances the random sequence by one. The child adds two to the internal state and advances the random sequence by one.
Now you can make any arbitrary tree of tasks, and those tasks each get their own random stream, there is no shared-between-task state or locking needed, and the whole thing is reproducible, even if parent and child tasks are scheduled arbitrarily. fork-ing and use of random numbers can be arbitrarily intermingled.
Makes sense. Do you have any particular implementations in mind that work this way?
I think this depends on the random number generator. For a counter-based RNG, the "internal state" is just a counter, so adding 1 or 2 would result in reusing random numbers in different streams.
Julia's random number generator does this. See https://github.com/JuliaLang/julia/blob/94a0ee8637b66ab67445...
That split function looks a lot more complicated. Thanks for the reference, though!
The SplitMix algorithm looks pretty useful. In Java, this is the built-in SplittableRandom class, and there seems to be an npm for it:
https://www.npmjs.com/package/splitmix
The complexity is because it is not a cryptographic pseudorandom generator.
If you have something cryptographic, than any basic operation on the internal state (ie. Increment by one) is enough to totally change the output stream in a way and outsider cannot predict.
You have to think about how your operations interact with other operations you might also do on the random state. Like what if you add one to the state, but someone else subtracts one from the state back to where you started, ooops! Or what if you create a new rng2 by adding one to the state of rng1. Then later you create rng3 by adding one to the state of rng1. Now rng2==rng3. Oops!
That's why I like the orignal idea you described of adding 1 and 2 and advancing each rng. This ensures that both streams are irreversibly altered which should make it very hard to accidentally misuse.
This seems like an area where a mutable API beats an immutable API. It's very easy to accidentally reuse old states when doing functional programming. On the other hand, if you need a way to serialize the RNG, (to send it to another task, perhaps) then the risk of reusing states comes back again.
The counter-based RNG I was looking at is an immutable API. It makes it easy to initialize generators in separate tasks by feeding each one a unique ID, but figuring out how to do a split operation is harder. Conceptually, the way to go is to multiply the key by 2 and add either 0 or 1 for each branch, to give them unique IDs. (This is called a pedigree.) However, for unbalanced trees, you will run out of bits. Figuring out how to do deal with that seems tricky?
The LXM generator paper (non-crypto) looks like good reading:
https://dl.acm.org/doi/pdf/10.1145/3485525
They initialize the new child with the next random values of the parent. There is an extra parameter that they use to add more input bits, to reduce the probability of overlap.
Another fun one for reproducibility -- rounding. It can happen when compiled for multiple architectures, compiling a second time with different optimizations, .... Things like normal random numbers are generated through _some_ kind of rejection sampling, and crossing that threshold from different rounding behavior will give you a wildly different result. Even if all your application code is tolerant of small perturbations, the result isn't reasonably reproducible.
Another way things go wrong with the prng tree idea (assuming the implementation is correct and you actually have independent streams) is race conditions in other parts of your code. E.g., say you have two workers reading a queue and using fancy tree-based randomness. You don't have "race" conditions (data races) in safe Rust without a compiler bug, but the language doesn't define which worker will read which item from the queue. You wind up using a different part of the stream for different inputs.
With the counter-based RNG approach, apparently one idea is that you uniquely identify child nodes in your tree somehow. That is, each work unit is a node with a unique ID that's deterministically assigned and has nothing to do with random number generation at all. Then you use that to pick the random stream.
An API that uses split or jump seems a little easier to screw up.
You may want to have a look at how they do Extended Keys over in bitcoin: https://learnmeabitcoin.com/technical/keys/hd-wallets/extend...