Simple proof that GUID is not unique

Question

I d like to prove that a GUID is not unique in a simple test program  I expected the following code to run for hours  but it s not working  How can I make it work   BigInteger begin   new BigInteger  long 0   BigInteger end   new BigInteger  340282366920938463463374607431768211456  10      2 128 for begin  begin lt end  begin      Console WriteLine System Guid NewGuid   ToString       I m using C

User · Answer

Well if the running time of 83 billion years does not scare you  think that you will also need to store the generated GUIDs somewhere to check if you have a duplicate  storing 2 128 16-byte numbers would only require you to allocate 4951760157141521099596496896 terabytes of RAM upfront  so imagining you have a computer which could fit all that and that you somehow find a place to buy terabyte DIMMs at 10 grams each  combined they will weigh more than 8 Earth masses  so you can seriously shift it off the current orbit  before you even press  Run   Think twice

User · Answer

Counting to 2 128 - ambitious   Lets imagine that we can count 2 32 IDs per second per machine - not that ambitious  since it s not even 4 3 billion per second  Lets dedicate 2 32 machines to that task  Furthermore  lets get 2 32 civilisations to each dedicate the same resources to the task   So far  we can count 2 96 IDs per second  meaning we will be counting for 2 32 seconds  a little over 136 years    Now  all we need is to get 4 294 967 296 civilisations to each dedicate 4 294 967 296 machines  each machine capable of counting 4 294 967 296 IDs per second  purely to this task for the next 136 years or so - I suggest we get started on this essential task right now  -

User · Answer

Here s a nifty little extension method that you can use if you want to check guid uniqueness in many places in your code   internal static class GuidExt       public static bool IsUnique this Guid guid                while  guid    Guid NewGuid                        return false            To call it  simply call Guid IsUnique whenever you generate a new guid     Guid g   Guid NewGuid    if   g IsUnique          throw new GuidIsNotUniqueException           heck  I d even recommend calling it twice to make sure it got it right in the first round

User · Answer

Go to the cryogenics lab in the New York City  Freeze yourself for  roughly  1990 years  Get a job at Planet Express  Buy a brand-new CPU  Build a computer  run the program  and place it in the safe place with an pseudo-perpetual motion machine like the doomsday machine  Wait until the time machine is invented  Jump to the future using the time machine  If you bought 1YHz 128bit CPU  go to 3 938 453 320 days 20 hours 15 minutes 38 seconds 463 ms 463   s 374 ns 607 ps after when you started to run the program       PROFIT          It takes at least 10 783 127 years even if you had 1YHz CPU which is 1 000 000 000 000 000  or 1 125 899 906 842 624 if you prefer to use binary prefix  times faster than 1GHz CPU   So rather than waiting for the compute finished  it would be better to feed pigeons which lost their home because other n pigeons took their home      Or  you can wait until 128-bit quantum computer is invented  Then you may prove that GUID is not unique  by using your program in reasonable time maybe

User · Answer

The odds of a bug in the GUID generating code are much higher than the odds of the algorithm generating a collision  The odds of a bug in your code to test the GUIDs is even greater  Give up

User · Answer

You could hash the GUIDs  That way  you should get a result much faster   Oh  of course  running multiple threads at the same time is also a good idea  that way you ll increase the chance of a race condition generating the same GUID twice on different threads

User · Answer

You can show that in O 1  time with a variant of the quantum bogosort algorithm   Guid g1   Guid NewGuid    Guid g2   Guid NewGuid    if g1    g2  Universe Current Destroy

User · Answer

Update   As the comments below point out  newer MS GUIDs are V4 and do not use the MAC address as part of the GUID generation  I haven t seen any indication of a V5 implementation from MS though  so if anyone has a link confirming that let me know   WIth V4 though  time is still a factor though  and the odds against duplication of GUIDs remains so small as to be irrelevant for any practical usage  You certainly would not be likely to ever generate a duplicate GUID from just a single system test such as the OP was trying to do         Most of these answers are missing one vital point about Microsoft s GUID implementation  The first part of the GUID is based on a timestamp and another part is based on the MAC address of the network card  or a random number if no NIC is installed     If I understand this correctly  it means that the only reliable way to duplicate a GUID would be to run simultainous GUID generations on multiple machines where the MAC addresses were the same AND where the clocks on both systems were at the same exact time when the generation occured  the timestamp is based on milliseconds if I understand it correctly      even then there are a lot of other bits in the number that are random  so the odds are still vanishingly small   For all practical purposes the GUIDs are universally unique   There is a pretty good description of the MS GUID over at  The Old New Thing  blog

User · Answer

Personally  I think the  Big Bang  was caused when two GUIDs collided

User · Answer

Since part of Guid generation is based on the current machine s time  my theory to get a duplicate Guid is    Perform a clean installation of Windows Create a startup script that resets the time to 2010-01-01 12 00 00 just as Windows boots up  Just after the startup script  it triggers your application to generate a Guid   Clone this Windows installation  so that you rule out any subtle differences that may occur in subsequent boot-ups  Re-image the hard drive with this image and boot-up the machine a few times

User · Answer

A GUID is theoretically non-unique  Here s your proof    GUID is a 128 bit number You cannot generate 2 128   1 or more GUIDs without re-using old GUIDs   However  if the entire power output of the sun was directed at performing this task  it would go cold long before it finished   GUIDs can be generated using a number of different tactics  some of which take special measures to guarantee that a given machine will not generate the same GUID twice  Finding collisions in a particular algorithm would show that your particular method for generating GUIDs is bad  but would not prove anything about GUIDs in general

User · Answer

Aren t you all missing a major point   I thought GUIDs were generated using two things which make the chances of them being Globally unique quite high  One is they are seeded with the MAC address of the machine that you are on and two they use the time that they were generated plus a random number   So unless you run it on the actual machine and run all you guesses within the smallest amount of time that the machine uses to represent a time in the GUID you will never generate the same number no matter how many guesses you take using the system call   I guess if you know the actual way a GUID is made would actually shorten the time to guess quite substantially   Tony

User · Answer

Here s a solution  too   int main       QUuid uuid    while    uuid   QUuid  createUuid       QUuid  createUuid           std  cout  lt  lt   Aha  I ve found one     lt  lt  qPrintable  uuid toString      lt  lt  std  endl      Note  requires Qt  but I guarantee that if you let it run long enough  it might find one    Note note  actually  now that I m looking at it  there may be something about the generation algorithm that prevents two subsequently generated uuids that collide--but I kinda doubt it

User · Answer

for begin  begin lt end  begin      Console WriteLine System Guid NewGuid   ToString       You aren t incrementing begin so the condition begin  lt  end is always true

User · Answer

The program  albeit its errors  shows proof that a GUID is not unique   Those that try to prove the contrary are missing the point   This statement just proves the weak implementation of some of the GUID variations   A GUID is not necessary unique by definition  it is highly unique by definition   You just refined the meaning of highly   Depending on the version  the implementator  MS or others   use of VM s  etc your definition of highly changes    see link in earlier post   You can shorten your 128 bit table to prove your point   The best solution is to use a hash formula to shorten your table with duplicates  and then use the full value once the hash collides and based on that re-generate a GUID   If running from different locations  you would be storing your hash full key pairs in a central location     Ps  If the goal is just to generate x number of different values  create a hash table of this width and just check on the hash value

User · Answer

Not to p  s on the bonfire here  but it does actually happen  and yes  I understand the joking you have been giving this guy  but the GUID is unique only in principle  I bumped into this thread because there is a bug in the WP7 emulator which means every time it boots it gives out the SAME GUID the first time it is called  So  where in theory you cannot have a conflict  if there is a problem generating said GUI  then you can get duplicates  http   forums create msdn com forums p 92086 597310 aspx 597310

User · Answer

GUIDs are 124 bits because 4 bits hold the version number

User · Answer

If GUID collisions are a concern  I would recommend using the ScottGuID instead

User · Answer

Have you tried begin   begin   new BigInteger  long 1  in place of begin

User · Answer

If the number of UUID being generated follows Moore s law  the impression of never running out of GUID in the foreseeable future is false   With 2   128 UUIDs  it will only take 18 months   Log2 2 128     192 years  before we run out of all UUIDs   And I believe  with no statistical proof what-so-ever  in the past few years since mass adoption of UUID  the speed we are generating UUID is increasing way faster than Moore s law dictates  In other words  we probably have less than 192 years until we have to deal with UUID crisis  that s a lot sooner than end of universe    But since we definitely won t be running them out by the end of 2012  we ll leave it to other species to worry about the problem

User · Answer

The only solution to prove GUIDs are not unique would be by having a World GUID Pool  Each time a GUID is generated somewhere  it should be registered to the organization  Or heck  we might include a standardization that all GUID generators needs to register it automatically and for that it needs an active internet connection

User · Answer

Presumably you have reason to be believe that the algorithm for producing Guids is not producing truly random numbers  but is in fact cycling with a period  lt  lt  2 128    e g  RFC4122 method used to derive GUIDs which fixes the values of some bits   Proof of cycling is going to depend upon the possible size of the period   For small periods  hash table of hash GUID  -  GUID with replacement on collision if GUIDs do not match  terminate if they do  might be an approach  Consider also only doing the replacement a random fraction  of the time   Ultimately if the maximum period between collisions is large enough  and isn t known in advance  any method is only going to yield a probability that the collision would be found if it existed    Note that if the method of generating Guids is clock based  see the RFC   then it may not be possible to determine if collisions exist because either  a  you won t be able to wait long enough for the clock to wrap round  or  b  you can t request enough Guids within a clock tick to force a collision   Alternatively you might be able to show a statistical relationship between the bits in the Guid  or a correlation of bits between Guids  Such a relationship might make it highly probable that the algorithm is flawed without necessarily being able to find an actual collision    Of course  if you just want to prove that Guids can collide  then a mathematical proof  not a program  is the answer

User · Answer

Of course GUIDs can collide  Since GUIDs are 128-bits  just generate 2 128   1 of them and by the pigeonhole principle there must be a collision   But when we say that a GUID is a unique  what we really mean is that the key space is so large that it is practically impossible to accidentally generate the same GUID twice  assuming that we are generating GUIDs randomly    If you generate a sequence of n GUIDs randomly  then the probability of at least one collision is approximately p n    1 - exp -n 2   2   2 128   this is the birthday problem with the number of possible birthdays being 2 128        n     p n  2 30 1 69e-21 2 40 1 77e-15 2 50 1 86e-10 2 60 1 95e-03   To make these numbers concrete  2 60   1 15e 18  So  if you generate one billion GUIDs per second  it will take you 36 years to generate 2 60 random GUIDs and even then the probability that you have a collision is still 1 95e-03  You re more likely to be murdered at some point in your life  4 76e-03  than you are to find a collision over the next 36 years  Good luck

User · Answer

This will run for a lot more than hours  Assuming it loops at 1 GHz  which it won t - it will be a lot slower than that   it will run for 10790283070806014188970 years  Which is about 83 billion times longer than the age of the universe   Assuming Moores law holds  it would be a lot quicker to not run this program  wait several hundred years and run it on a computer that is billions of times faster  In fact  any program that takes longer to run than it takes CPU speeds to double  about 18 months  will complete sooner if you wait until the CPU speeds have increased and buy a new CPU before running it  unless you write it so that it can be suspended and resumed on new hardware

User · Answer

Any two GUIDs are very likely unique  not equal    See this SO entry  and from Wikipedia     While each generated GUID is not   guaranteed to be unique  the total   number of unique keys  2 128 or   3 4  10 38  is so large that the probability of the same number being   generated twice is very small  For   example  consider the observable   universe  which contains about 5  10 22   stars  every star could then have   6 8  10 15 universally unique GUIDs    So probably you have to wait for many more billion of years  and hope that you hit one before the universe as we know it comes to an end

User · Answer

Kai  I have provided a program that will do what you want using threads  It is licensed under the following terms  you must pay me  0 0001 per hour per CPU core you run it on  Fees are payable at the end of each calendar month  Please contact me for my paypal account details at your earliest convenience   using System  using System Collections Generic  using System Linq   namespace GuidCollisionDetector       class Program               static void Main string   args                          var reserveSomeRam   new byte 1024   1024   100          This indeed has no effect               Console WriteLine   0 u  - Building a bigHeapOGuids    DateTime Now                  Fill up memory with guids              var bigHeapOGuids   new HashSet lt Guid gt                 try                               do                                       bigHeapOGuids Add Guid NewGuid                       while  true                             catch  OutOfMemoryException                                   Release the ram we allocated up front                     Actually  these are pointless too                    GC KeepAlive reserveSomeRam                     GC Collect                              Console WriteLine   0 u  - Built bigHeapOGuids  contains  1  of them    DateTime Now  bigHeapOGuids LongCount                      Spool up some threads to keep checking if there s a match                 Keep running until the heat death of the universe              for  long k   0  k  lt  Int64 MaxValue  k                                  for  long j   0  j  lt  Int64 MaxValue  j                                          Console WriteLine   0 u  - Looking for collisions with  1  thread s        DateTime Now  Environment ProcessorCount                       System Threading Tasks Parallel For 0  Int32 MaxValue   i    gt                                                if  bigHeapOGuids Contains Guid NewGuid                                 throw new ApplicationException  Guids collided  Oh my gosh                                                                      Console WriteLine   0 u  - That was another  1  attempts without a collision    DateTime Now    long Int32 MaxValue    Environment ProcessorCount                                               Console WriteLine  Umm    why hasn t the universe ended yet                         PS  I wanted to try out the Parallel extensions library  That was easy   And using OutOfMemoryException as control flow just feels wrong   EDIT  Well  it seems this still attracts votes  So I ve fixed the GC KeepAlive   issue  And changed it to run with C  4   And to clarify my support terms  support is only available on the 28 Feb 2010  Please use a time machine to make support requests on that day only   EDIT 2 As always  the GC does a better job than I do at managing memory  any previous attempts at doing it myself were doomed to failure

User · Answer

I don t understand why no one has mentioned upgrading your graphics card    Surely if you got a high-end NVIDIA Quadro FX 4800 or something  192 CUDA cores  this would go faster      Of course if you could afford a few NVIDIA Qadro Plex 2200 S4s  at 960 CUDA cores each   this calculation would really scream   Perhaps NVIDIA would be willing to loan you a few for a  Technology Demonstration  as a PR stunt     Surely they d want to be part of this historic calculation

User · Answer

For me   the time it takes for a single core to generate a UUIDv1 guarantees it will be unique   Even in a multi core situation if the UUID generator only allows one UUID to be generated at a time for your specific resource  keep in mind that multiple resources can totally utilize the same UUIDs however unlikely since the resource inherently part of the address  then you will have more than enough UUIDs to last you until the timestamp burns out   At which point I really doubt you would care

User · Answer

If you re worried about uniqueness you can always purchase new GUIDs so you can throw away your old ones   I ll put some up on eBay if you d like

User · Answer

But do you have to be sure you have a duplicate  or do you only care if there can be a duplicate   To be sure that you have two people with the same birthday  you need 366 people  not counting leap year    For there to be a greater than 50  chance of having two people with the same birthday you only need 23 people   That s the birthday problem   If you have 32 bits  you only need 77 163 values to have a greater than 50  chance of a duplicate   Try it out   Random baseRandom   new Random 0    int DuplicateIntegerTest int interations        Random r   new Random baseRandom Next         int   ints   new int interations       for  int i   0  i  lt  ints Length  i                  ints i    r Next              Array Sort ints       for  int i   1  i  lt  ints Length  i                  if  ints i     ints i - 1               return 1            return 0     void DoTest         baseRandom   new Random 0       int count   0      int duplicates   0      for  int i   0  i  lt  1000  i                  count            duplicates    DuplicateIntegerTest 77163             Console WriteLine   0  iterations had  1  with duplicates   count  duplicates      1000 iterations had 737 with duplicates   Now 128 bits is a lot  so you are still talking a large number of items still giving you a low chance of collision   You would need the following number of records for the given odds using an approximation    0 8 billion billion for a 1 1000 chance of a collision occurring 21 7 billion billion for 50  chance of a collision occurring 39 6 billion billion for 90  chance of a collision occurring   There are about 1E14 emails sent per year so it would be about 400 000 years at this level before you would have a 90  chance of having two with the same GUID  but that is a lot different than saying you need to run a computer 83 billion times the age of the universe or that the sun would go cold before finding a duplicate

[c#] Simple proof that GUID is not unique

Examples related to c#

Examples related to guid