Re: Concurrent access to /dev/urandom

[David Lang]

On Tue, 7 Dec 2004, Bernard Normier wrote:

> I am just trying to generate UUIDs (without duplicates, obviously).

pulling data from /dev/random or /dev/urandom will not ensure that you 
don't have duplicates.

the key factor in a random number generator is that the next number to 
coem out must be (sufficiantly) unpredictable. this says nothing about it 
being unique, in fact it says that if you pull the number 1234 the first 
time you should have the exact same odds of pulling 1234 the second time 
as you have in pulling 4321 (or any other number)

no much of the time you can get away with useing a random number generator 
like this, but if you pull enough numbers you will get collisions.

remember the birthday paradox. it says that if you get a group of 26 
people in a room you have about a 50% chance that two of these people have 
the same birthday.

now that's only with numbers in the range of 1-365 if you pull 16 bit 
numbers (1-65536) you will need a much larger group to see the problem, 
but if you pull enough you WILL see the problem eventually.

David Lang

--
There are two ways of constructing a software design. One way is to make it so simple that there are obviously no deficiencies. And the other way is to make it so complicated that there are no obvious deficiencies.
 -- C.A.R. Hoare
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/