[riot-devel] To global seed or not to global seed

Cenk Gündoğan list-riot at cgundogan.de
Wed Mar 8 00:53:09 CET 2017


Hey,

oh sure, here it follows:

```
The ISO C standard rand() and srand() functions allow per-process
pseudo-random streams shared by all threads. Those two functions need
not change, but there has to be mutual-exclusion that prevents
interference between two threads concurrently accessing the random
number generator.

With regard to rand(), there are two different behaviors that may be
wanted in a multi-threaded program:

1. A single per-process sequence of pseudo-random numbers that is shared
   by all threads that call rand()
2. A different sequence of pseudo-random numbers for each thread that
   calls rand()

This is provided by the modified thread-safe function based on whether
the seed value is global to the entire process or local to each thread.
```
See: http://pubs.opengroup.org/onlinepubs/9699919799/functions/rand.html

The above prose makes me wonder: our current
global-state-PRNG-implementations do AFAIK not provide mutual
exclusion.. So, two threads accessing the PRNG could get in each other's
way (?). And this is not just about `random_init()`, but all calls that
modify an existing PRNG sequence, such as a simple `rand()`.

Just as info: in the above link it says:

```
The drand48() and random() functions provide much more elaborate
pseudo-random number generators.
```

and those do actually allow to intuitively set custom states, or do
mutual exclusion:
http://pubs.opengroup.org/onlinepubs/9699919799/functions/random.html
http://pubs.opengroup.org/onlinepubs/9699919799/functions/drand48.html

Cheers,
Cenk

On 17-03-08 00:26:02, Thomas C. Schmidt wrote:
> Hi Cenk,
> 
> thanks for bringing this up!
> 
> Can you add the POSIX perspective to the rand* calls? I guess it would be
> beneficial to remain close to what POSIX describes for an API.
> 
> Cheers,
>  Thomas
> 
> On 08.03.2017 00:18, Cenk Gündoğan wrote:
> > Dear RIOTers,
> > 
> > for quite some time now we have semi-active discussions (mostly on
> > GitHub) about various PRNG and seeding concepts. In this mail I merely
> > want to focus on the scope of our PRNG implementations' seeds/states.
> > 
> > Currently, all function calls in our PRNG implementations and the
> > abstraction layer `sys/random` do *not* allow to pass a custom state.
> > This means, there is *one* global state, that is overwritten with
> > successive calls to `random_init()`, not necessarily from the same
> > thread. At the moment, `auto_init` is the only instance, that calls
> > `random_init` (albeit with `0`, but this is another story). So
> > everything seems to be OK for now (?), but will it stay this way? In the
> > current state, and to guarantee deterministic PRNG sequences, all calls
> > to `random_init()` *must* be ignored, but not the first. Of course, this
> > can be done in various ways ..
> > 
> > 1) we can define it as BCP to *not* use `random_init()` if `auto_init`
> >    is used
> >    => it's hard to guarantee a one-time call to `random_init()` as human
> >    do surely err (especially if several nested modules are involved).
> > 
> > 2) check within `random_init()` for an unitialized state and only
> >    initialize if such a state is prevalent. Ignore the call to
> >    `random_init()` if the PRNG was initialized before.
> >    => this introduces a further check that is done with each call to
> >    `random_init()` and feigns to the user a freshly initialized PRNG.
> > 
> > In contrast to the current procedure of having a global state, we rather
> > should opt to allow local states for each thread (not excluding a global
> > state). Although I have no special use case in mind at the moment, I
> > believe that it should be possible to let user applications initialize
> > "their own PRNG" to produce deterministic sequences. With the current
> > approach, the sequence of our PRNG is shared with all available threads.
> > This means, a user application would share the sequence with the network
> > stack's NDP, RPL, TCP, ... implementations.
> > 
> > IMO, our random API needs to be extended to provide function definitions
> > that also allow the passing of local seed states. However, different
> > PRNGs use different kind / different numbers of seeds. A "local scope"
> > seed struct would need to encapsulate enough information to be usable
> > with all PRNGs; and that's the part that deserves some thinking.
> > 
> > What is your opinion on having / allowing local scope seed states?
> > 
> > Cheers,
> > Cenk
> > 
> 
> -- 
> 
> Prof. Dr. Thomas C. Schmidt
> ° Hamburg University of Applied Sciences                   Berliner Tor 7 °
> ° Dept. Informatik, Internet Technologies Group    20099 Hamburg, Germany °
> ° http://www.haw-hamburg.de/inet                   Fon: +49-40-42875-8452 °
> ° http://www.informatik.haw-hamburg.de/~schmidt    Fax: +49-40-42875-8409 °
> _______________________________________________
> devel mailing list
> devel at riot-os.org
> https://lists.riot-os.org/mailman/listinfo/devel
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 833 bytes
Desc: not available
URL: <http://lists.riot-os.org/pipermail/devel/attachments/20170308/92d0c533/attachment.sig>


More information about the devel mailing list