1

Typically, the seeding of srand() is done by:

srand(time(NULL));

In my case, I use random numbers to generate an identifier for my client process at runtime on the network. The process sometimes restarts and generates a new identifier. As the number of clients increases, there's a good chance that two clients call srand(time(NULL)) within the same sec, which creates two identical identifiers, or a collision as seen by the server side. Some people suggested a finer resolution:

srand((time.tv_sec * 1000) + (time.tv_usec / 1000));

But The trouble here is that the seed will repeat every 24 days or so, and when the number of machines is large enough, there's still a chance of collision. There's another solution:

srand(time.tv_usec * time.tv_sec);

But this seems problematic to me too because the the modulus of this product (the higher bits overflow and get abandoned) is not evenly distributed within the range of the unsigned int seed value. For example, for every sec, time.tv_usec == 0 leads to the same seed.

So is there a way to seed srand() in my case?

Edit: the client runs on Linux, Windows, Android and iOS, so /dev/random or /dev/urandom isn't always available.

P.S. I'm aware of the GUID/UUID approach, but I'd like to know if it's possible to just seed srand() properly in this case.

Community
  • 1
  • 1
Aufheben
  • 857
  • 7
  • 18
  • Use a crytpographic RNG to seed `srand()` – toasted_flakes Jan 09 '14 at 12:40
  • what about xoring the time(NULL) with some computer specific identifier? – V-X Jan 09 '14 at 12:47
  • If you're dependent on your random numbers to have a any of: even distribution, unpredictability or relative uniqueness between runs no standard functions will work and clever seeding won't help that much either. Find a library that supports all the platforms that you run on and use that. You'll find good randomness functions in most cryptographic libraries. Or find a solution that doesn't require random numbers. – Art Jan 09 '14 at 13:16
  • It doesn't sound like you want a random number at all. It sounds like you want to ask the server to return a sequence number (or the secure digest of a sequence number if security is a concern). – sh1 Jan 12 '14 at 05:32
  • @sh1 Yes, that would work well too. – Aufheben Jan 12 '14 at 09:29

5 Answers5

2

srand and rand are simply not appropriate if you have a lot of processes or threads that need to have pseudo-randomness that is independent between them.

On POSIX systems you can use the rand48 family of functions like jrand48 that have known state size. If you depend on process, thread and machine independence you should use significant bits from the process ID, thread ID, IP address and time to initialize the state. jrand[48] takes (and modifies) a state of three short, so it should be relatively simple to seed these with the different quanties.

All but one of the systems that you list are POSIX, so this should work there. What would be an adequate fallback for Windows systems, I don't know.

Jens Gustedt
  • 76,821
  • 6
  • 102
  • 177
2

If two random number generators never have collisions, they're not random. It would be like playing 'snap' but never getting a match.

So, what you want is a worse, rather than a better random number generator. Using GUIDs is indeed one approach that should entirely remove the problem for you.

But, If you're happy just reducing the chance of collisions, rather than eliminating them entirely you could use the machine's IP address (or processor serial number, or somesuch) as part of the seed.

Roddy
  • 66,617
  • 42
  • 165
  • 277
1

If you are writing for linux platform, use /dev/random and /dev/urandom to get random numbers. Unlike srand(), /dev/random and /dev/urandom uses noise generated from hardware peripherals to generate random numbers. srand() uses seed supplied as argument to generate random number.

Chinna
  • 3,930
  • 4
  • 25
  • 55
  • The client runs on Linux, Windows, Android and iOS, so /dev/random or /dev/urandom isn't always available. – Aufheben Jan 09 '14 at 12:45
0

You have two domains: clients and processes. Therefore you need a unique identifier for each one. Processes obviously can be done with the process-id. For clients, I suggest using the MAC address, which MUST be unique for each network interface. I believe that all the platforms you list support sockets, so the SIOCGIFHWADDR ioctl may be supported.

The only problem is that MAC addresses are 48 bits and PIDs are typically 32 bits, so you have to pick the highest entropy bits of the two values to use for your srand seed. I suggest the lower 16 bits of the PID and the lower 16 bits of the MAC address.

Chris J. Kiick
  • 1,487
  • 11
  • 14
0

I think you'll be interested in the paper "Parallel Random Numbers: As Easy as 1, 2, 3".

Quoting from the abstract: "All our PRNGs pass rigorous statistical tests (including TestU01’s BigCrush) and produce at least 264 unique parallel streams of random numbers, each with period 2128 or more"

loreb
  • 1,327
  • 1
  • 7
  • 6
  • That does look interesting, although I was a little confused when I saw 264 and 2128, which turn out to be 2 ^ 64 and 2 ^ 128. :P – Aufheben Jan 10 '14 at 16:13