Saturday, March 03, 2018

[ttjsbzma] Avoiding the birthday paradox

Each person draws with replacement from an urn containing N balls.  For a given population size, how large should N be so that the probability of collision is smaller than some given small probability?  Of course, larger than Population^2 because probabilities are around 50% there.

If we want collisions to "never" happen, what should that small probability be?  2^-128? 2^-256?  Randomly chosen 128-bit UUIDs only offer 2^64 collision resistance, probably OK for each human on earth choosing just one, but not enough for (say) tagging rapid transactions.

Inspiration was, how does a galactic civilization with a population on the order of 2^114 choose unique identifiers, e.g., the future equivalent of Social Security Numbers, for each person in a distributed way (not requiring central coordination because communication might be expensive)?  Or, how should it assign IP addresses to its galactic network of computers (though that might be more difficult, also requiring solving routing)?

No comments :