2

I was reading this section and the last paragraph stated that the example code was not thread-safe. My question is: wouldn't that help increase its randomness (i.e. if multiple threads were to concurrently execute those lines)?

Adib Saad
  • 552
  • 3
  • 10
  • have you ever heard of the term race-conditions? – SandBag_1996 Aug 23 '12 at 21:12
  • Yes I have; but that's the point. Aren't race-conditions potentially a source of random activity? Couldn't that add another layer of randomness to the code? – Adib Saad Aug 23 '12 at 21:14
  • A PNRG may be designed to have nice properties of its outputs. That does not necessarily mean its intermediate calculation states are random, which is what you a reading if you have race conditions. – TJD Aug 23 '12 at 21:16
  • 5
    There's also no guarantee that your race conditions are random. You could easily have timing dependencies that reproduce exactly the same race conditions periodically. – TJD Aug 23 '12 at 21:18

4 Answers4

7

PRNGs are carefully engineered (well, maybe not RANDU) to yield predictable and sufficiently randomly distributed results. They don't have to be truly random, they just have to satisfy statistical quality tests, yield a large-enough period and be deterministic with the same seed.

If you happen to use the generator from multiple threads simultaneously all those guarantees go down the drain. Most importantly you cannot have a reproducible result (which is extremely important in simulations). Then the state might change or perhaps you get the same number twice in different threads, those things.

You definitely don't want to go there. Create one PRNG per thread (preferrably with seeds that are linearly independent).

Joey
  • 344,408
  • 85
  • 689
  • 683
  • So if I make a non-thread safe PRNG (and it doesn't corrupt the internal state, as Sean mentioned), could I obtain an 'almost' RNG? – Adib Saad Aug 23 '12 at 21:19
  • There is no reason to even try doing that. For one, thread-unsafety is pretty unpredictable so you have nothing to rely on what could happen. And secondly, PRNGs usually have very specific uses and those uses *need* the guarantees they make about the sequence. – Joey Aug 23 '12 at 21:22
  • 3
    @someDude Race conditions aren't bit scramblers. The most likely result is that some intermediate values will keep getting reused. The pattern in which it happens will be unpredictable, so there is a random element there. But that old "nine nine nine nine" [Dilbert cartoon](http://search.dilbert.com/comic/Random%20Nine) still comes to mind. – Sean U Aug 23 '12 at 21:27
4

One possible side effect in non-threadsafe random number generators is that you can corrupt the internal state in some way. For example, if you're accessing the same instance of .NET's Random from two different threads, it's possible to put it in a state where it just keeps returning 0 repeatedly.

In the RNG you link, it doesn't look like that particular problem can happen but it might possible for some degenerate concurrent access pattern to set m_z or m_w to 0, which according to the comments would also be bad.

Sean U
  • 6,730
  • 1
  • 24
  • 43
0

You definitely could obtain entropy from thread timing generation, but it's a very bad idea to mix entropy collection and pseudo-random number generation in ways where the former could interfere with the otherwise-provable properties of the latter - much like what Joey said. The reason I'm adding a new answer is that you might alternatively consider mixing real entropy with your PRNG (either just as a seed, or periodically introducing more), and collecting real timing information from different threads is one possible source of entropy. It should however be done rigorously (with proper locking or lock-free atomic operations to store the results), not by invoking undefined behavior and hoping that gets you entropy.

R.. GitHub STOP HELPING ICE
  • 208,859
  • 35
  • 376
  • 711
0

There are many ways in which code is non-thread safe.

One way is that threads fail to see writes to memory made by other threads.

We might find then a random number generation producing all zeros, because it never "sees" the work done by other threads.