Only if you assume a monotonic clock ...
--- The fact that there's a Highway to Hell but only a Stairway to Heaven says a lot about anticipated traffic volume. >-----Original Message----- >From: sqlite-users [mailto:sqlite-users- >boun...@mailinglists.sqlite.org] On Behalf Of J. King >Sent: Friday, 24 November, 2017 20:54 >To: SQLite mailing list >Subject: Re: [sqlite] "BIGINT" doesn't act like INTEGER on table >creation [Bug] > >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
