I've been implementing a network protocol, and I require packets to have unique identifiers. So far, I've just been generating random 32-bit integers, and assuming that it is astronomically unlikely that there will be a collision during the lifespan of a program/connection. Is this generally considered an acceptable practice in production code, or should one devise a more complex system to prevent collisions?
Beware the birthday paradox.
Suppose you are generating a sequence of random values (uniformly, independently) from a set of size N (N = 2^32 in your case).
Then, the rule of thumb for the birthday paradox states that once you have generated about sqrt(N) values, there is at least a 50% chance that a collision has occurred, that is, that there are at least two identical values in the generated sequence.
For N = 2^32, sqrt(N) = 2^16 = 65536. So after you have generated about 65k identifiers, it is more likely that two of them collide than not! If you generate an identifier per second, this would happen in less than a day; needless to say, many network protocols operate way faster than that.
It is widely considered acceptable to rely on random numbers being unique if those numbers have enough bits. There are cryptographic protocols where repeating a random number will break the entire security. And as long as there aren't serious vulnerabilities in the random number generator being used, that hasn't been a problem.
One of the algorithms for generating UUIDs will effectively generate an ID consisting of 122 random bits and assume it will be unique. And two of the other algorithms rely on a hash value truncated to 122 bits being unique, which has roughly the same risk of collisions.
So there are standards relying on 122 bits being enough to make a random ID unique, but 32 bits is definitely not enough. With 32 bit IDs it only takes about 2¹⁶ IDs before the risk of a collision reaches 50% because with 2¹⁶ IDs there will be close to 2³¹ pairs each of which could be a collision.
Even 122 bits is less than I would recommend in any new design. If following some standardization is important to you, then use UUIDs. Otherwise use something larger than 122 bits.
The SHA1 hash function with an output of 160 bits is no longer considered secure which is in part because 160 bits is not enough to guarantee uniqueness of the outputs. Modern hash functions have outputs from 224 to 512 bits. Randomly generated IDs should aim for the same sizes to ensure uniqueness with a good safety margin.
I would call this bad practice. Random number generates simply don't create unique numbers, they just create random numbers. A random distribution is likely to include some duplicates. You can make this circumstance acceptably unlikely by adding in an element of time. If you get the current time from the system clock in milliseconds. Something like this:
parseToInt(toString(System.currentTimeMillis()) + toString(Random.makeInt()))
Will go a long way. Obviously to truly guarantee uniqueness you need to use UUID/GUID. But they can be expensive to generate, the above is likely sufficient, as the only possibility of overlap, is if the random generate had a duplicate in the same millisecond.
It depends on both the probability of failure and the consequences of failure.
I remember a debate between software and hardware people where the hardware people considered that an algorithm with a small probability of wrong results (something like 1 failure in 100 years) was acceptable, and the software people thought this was anathema. It turned out that the hardware folks routinely calculated expected failure rates, and were very used to the idea that everything would give wrong answers occasionally, e.g. due to disturbances caused by cosmic rays; they found it strange that software folks expected 100% reliability.
Sure, you've got pretty low probabilities of two random 32-bit integers being sequential but it's not completely impossible. The appropriate engineering decision is based on what the consequences of collisions would be, an estimate of the volume of numbers you're generating, the lifetime over which uniqueness is required & what happens if a malicious user starts attempting to cause collisions.
It can be acceptable to assume that random numbers will be unique but you have to be careful.
Assuming your random numbers are equally distributed, the probability of a collision is roughly (n2/2)/k where n is the number of random numbers you generate and k is the number of possible values a "random" number can take.
You don't put a number on astronomically unlikely so lets take it as 1 in 230 (roughly on in a billion). Lets further say you generate 230 packets (if each packet represents about a kilobyte of data then this means about a terabyte of total data, large but not unimaginably so). We find we need a random number with at least 289 possible values.
Firstly your random numbers need to be big enough. A 32 bit random number can have at most 232 possible values. For a busy server that is nowhere near high enough.
Secondly your random number generator needs to have a sufficiently large internal state. If your random number generator only has a 32-bit internal state then no matter how big the value you generate from it you will still only get at most 232 possible values.
Thirdly if you need the random numbers to be unique across connections rather than just within a connection your random number generator needs to be well-seeded. This is especially true if your program is restarted frequently.
In general the "regular" random number generators in programming languages are not suitable for such use. The random number generators provided by cryptography libraries generally are.
built into some of the answers above is the assumption that the random number generator is indeed 'flat' - that the probability of any two numbers being the next one generated is the same.
That's probably not true for most random number generators. Most of which use some high order polynomial repeatedly applied to a seed.
That said, there are many systems out there that depend on this scheme, usually with UUID's. For example, every object and asset in Second Life has a 128 bit UUID, generated randomly, and they rarely collide.
A lot of people have already given high-quality answers, but I'd like to add a few minor points: first, @nomadictype 's point about the birthday paradox is excellent.
Another point: randomness isn't as straightforward to generate and define as people might ordinary assume. (In fact, there are actually statistical tests for randomness available).
With that said, it's important to be aware of the Gambler's Fallacy, which is a statistical fallacy where people assume that independent events somehow influence each other. Random events are generally statistically independent of each other - i.e. if you randomly generate a "10" it doesn't change your future probability of generating more "10"s in the least. (Maybe someone could come up with an exception to that rule, but I'd expect that that would be the case for pretty much all random number generators).
So my answer is that if you could assume that a sufficiently-long sequence of random numbers were unique, they wouldn't really be random numbers because that would be a clear statistical pattern. Also, it would imply that each new number isn't an independent event because if you generate, for example, a 10 that would mean that the probability of generating any future 10s would be 0% (it couldn't possibly happen), plus that would mean that you'd increase the odds of getting a number other than 10 (i.e. the more numbers you generate, the higher the probability of each of the remaining numbers becomes).
One more thing to consider: the chance of winning the Powerball off of playing a single game is, as I understand it, approximately 1 in 175 million. However, the odds of someone winning are considerably higher than that. You're more interested in the odds of someone "winning" (i.e. Being a duplicate) than in the odds of any particular number "winning"/being a duplicate.
It doesn't matter how many bits you use - you CANNOT guarantee that two "random" numbers will be different. Instead, I suggest that you use something like the IP address or other network address of the computer and a sequential number, preferably a HONKIN' BIG sequential number - 128 bits (obviously unsigned) sounds like a good start, but 256 would be better.
No, of course not. Unless the rng you're using samples without replacement, there's a chance - however small - of duplication.
protected by gnat Dec 31 '16 at 10:33
Thank you for your interest in this question.
Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).
Would you like to answer one of these unanswered questions instead?