Devise a way to share to implement a deterministic asynchronous rng

[altavir]

The generator state could be made a part of CoroutineContext.

[Shimuuar]

In fact we have two problems here:

1. We need PRNG which could generate multiple independent streams of random numbers from single seed
2. Way to assign these streams to coroutines (?) in deterministic manner.

Latter seems much more difficult than first and probably untractable in general.

PRNG choice

Since we need multiple independent stream counting RNG seems to be obvious choice.

In general PRNGs could be seen as triple of generator state s, transition function f : s → s which advances generator state by one step, and extraction function e :: s → {0,1}^n. Usually f is some complicated function whereas e is very simple, it just take some part of state.

Counting generators take another approach state is simple tuple of n machine words, say (k,n) and f just increments n. Randomness is generated by making e pseudorandom function, usually by using some crypographic hash function or something else from arsenal of cryptography. Multiple streams could be easily generated by taking different k

That's general idea. It's describe in more details in "Parallel Random Numbers: As Easy as 1, 2, 3" (2011). Like more work on such generators exist. Of course there's question of choosing concrete algorithms but problem is rather straightforward otherwise.

Assigning streams

Since I don't know kotlin I don't have any good idea. But I suspect achieving determinism using concurrent primitives would be impossible. To be more precise, it would be possible to write deterministic programs but it would be possible to write nondeterministic programs as well. And probably there's no way for compiler to distinguish such programs.

[Shimuuar]

Paper itself 2011-Parallel_Random_Numbers:_As_Easy_as_1,_2,_3.pdf

[altavir]

It seems like JVM supports splittable generator out of the box: https://docs.oracle.com/javase/8/docs/api/java/util/SplittableRandom.html. We need to test it though.

[altavir]

And here is an overview of algorithms in case we want to implement something for multiplatform: https://www.researchgate.net/publication/273188325_Fast_Splittable_Pseudorandom_Number_Generators

[Shimuuar]

And of course documentation omits most important part: algorithm being used.

Note that period is relatively short 2^64 which could pose problems for MC. As far a I understand extremely long periods are desired there.

Another point is quality of generator dieharder test suite is no longer state of art for testing PRNGs. I don't remember what is best test suite at the moment

[altavir]

It is core JVM class. Usually they do not guarantee specific implementation since it could depend on the platform and change between versions. In the end, we will probably want our own implementation, but we can use this one at first.

[altavir]

Proof of concept: c267372c70151a520455f988028fcc037d8618c9