We are an exploratory species, just past the solar system now, but perhaps one day we will look back and call our galaxy merely the first. There are many problems to solve along the way, and today we will look at one very small one. How do we assign IDs to devices (or any object) so the IDs are guaranteed to always be unique?
Being able to identify objects is a fundamental tool for building other protocols, and it also underpins manufacturing, logistics, communications, and security. Every ship and satellite needs an ID for traffic control and maintenance history. Every radio, router, and sensor needs an ID so packets have a source and destination. Every manufactured component needs an ID for traceability. And at scale, the count explodes: swarms of robots, trillions of parts, and oceans of cargo containers moving through a civilization’s supply chain.
One of the key functions of an ID is to differentiate objects from one another, so we need to make sure we don’t assign the same ID twice. Unique ID assignment becomes a more challenging problem when we try to solve it at the scale of the universe.
But we can try.
Random
The first and easiest solution is to pick a random number every time a device needs an ID.
This is so simple that it is likely the best solution; you can do this anytime, anywhere, without the need for a central authority or coordination of any kind.
The big issue, though, is that it’s possible for two devices to pick the same ID by chance. Fortunately, we have complete control over the size of the random number, and by extension, the probability of a collision. This means we can make the likelihood of a collision functionally zero.
You may say that “functionally zero” is not enough, that although the probability is small, it is not actually zero, and so you are concerned. But consider this example: The probability of you being struck by a meteorite right now is small but non-zero, and you might even call that a “reasonable” (if paranoid) concern. But are you worried that every human on Earth will be hit by a meteorite right now? That probability is also non-zero, yet it is so infinitesimally small that we treat it as an impossibility. That is how small we can make the probability of an ID collision.
So how small does this probability need to be before we are comfortable? It will be helpful to reframe the question: How many IDs can we generate before a collision is expected?
... continue reading