What about invalid and reused MAC addresses and devices with no MAC address at all? What about time resets to the epoch which are not restored, user time changes, daylight saving or leap seconds?
It sounds even more probabilistic than the probabilistic methods. Does anyone actually use it? > On Nov 25, 2017, at 4:54 AM, J. King <jk...@jkingweb.ca> wrote: > > Version 1 UUIDs only use a random number (16 bits) in the case of an > uninitialized clock sequence (a case which, ideally, should only occur the > first time a device generates a UUID). Version 1 UUIDs especially avoid using > random numbers; they are also not a shortening of longer input. > > In short, version 1 UUIDs are not a PRNG scheme, nor are they the same as > hash functions. > > I'm not a mathematician, and it's been a while since I've read the relevant > RFC, but I believe collisions in a proper, strict implementation of V1 UUIDs > are impossible by design until either a) the 60-bit timestamp overflows, or > b) the MAC address namespace is exhausted. It's not a matter of probability, > and it's only "a certainty" after the end of their design lifetime. > > Of course, UUIDs being of finite size, they will eventually be exhausted, and > a single machine may only generate 65536 identifiers in a 100-nanosecond span > of time. They will not, however, collide. > > On November 24, 2017 8:58:02 PM EST, Jean-Christophe Deschamps > <j...@antichoc.net> wrote: >> >> At 23:49 24/11/2017, you wrote: >> >>> On 11/24/17 5:26 PM, Jean-Christophe Deschamps wrote: >>> >>>> At 22:38 24/11/2017, you wrote: >>>>> One proof of the falsehood of your assertion is that we CAN fill a >>>>> database with some data using UIDs, and we will almost certainly not >> >>>>> get a collision, while you assertion we will. >>> >>>> This is an attempt at "proof by example". Keith is perfectly right >>>> --mathematically speaking-- and your "proof" doesn't hold water, I >>>> mean as a formal proof. The best proof that your "proof" isn't a >>>> proof is that you feel obliged to add "almost certainly". >>> >>> DISproof by example is a perfectly valid method. If someone makes a >>> claim that something is ALWAYS true, ONE counter example IS a >>> disproof. I said almost certainly as the chance of a collision isn't 0 >> >>> (to be able to say with certainty) but is most defintely less than the >> >>> 100% claimed. >> >> You're confusing one mathematical theorem and one practical statement. >> The first is the _mathematical_ fact that any PRNG (using any fixed >> number of random bits, which is what xUIDs are) will provide an >> infinite number of collisions with probability 1. This is definitely >> true. Of course here, the number of samples is implicitely infinite. >> >> Your practical statement is that you can "most certainly" ignore the >> possibility of collision when feeding 2^N xUIDs into a unique column >> without loosing sleep. That's good enough in practice. The issue with >> your "demonstration" is that 2^N is bounded, whatever finite N you >> choose. Hence you don't contradict what Keith said, you just say >> something different applying to restricted cases. You're speaking about >> >> practice, while Keith told about math. You're both right, each from his >> >> own point of view. But you can't claim to disproof a trivially true >> theorem this way, by changing its premices. >> >> An event with probability 10^-100000...000 (any finite number of >> zeroes) will occur at least once, provided you run enough tries. It'll >> occur an infinite number of times if you run an infinite number of >> tries. Else its probability would be zero. >> Your "disproof" amounts to say that 10^-100000...000 = 0 >> >> And neither Keith nor I ever said that an xUID collision will occur >> with probability 1 after 2^64 samples. That would be false and that's >> why people feel free to use xUIDs _AND_ sleep quietly. >> >> JcD >> >> _______________________________________________ >> sqlite-users mailing list >> sqlite-users@mailinglists.sqlite.org >> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users > > -- > Sent from my Android device with K-9 Mail. Please excuse my brevity. > _______________________________________________ > sqlite-users mailing list > sqlite-users@mailinglists.sqlite.org > http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users _______________________________________________ sqlite-users mailing list sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
