What are you using for a random number generator? If you're using a maximal length sequence, this will probably affect your analysis...
If I recall correctly, GUID generators incorporate information from the ethernet mac address of the device to ensure a unique GUID. Would this help in your scenario? Bill On Fri, Apr 24, 2009 at 12:13 PM, Serguei Osokine <serguei.osok...@efi.com> wrote: > On Thursday, April 23, 2009 Russ Weeks wrote: >> The theory is, the odds of generating 2 identical 64-bit numbers >> in the same nanosecond is less than the odds of generating 2 128- >> bit numbers over the lifetime of the system. If this is true, >> it's not clear to me. >> >> Can anybody suggest a way to quantify the likelyhood of collision >> in the second approach? > > First, you have to figure out how many different keys will be compared > to a given key over its lifetime. Say, your key lives for a year and > you generate 1,000 keys per second - so the key has to be compared to > about 3*10^10 different keys. The probability of the 128-bit (3*10^38) > key colliding to one of them is about 10^-28. For all keys generated > over a year's time, the total probability of at least one of them > colliding with another key will be 3*10^10 more, or about 3*10^-18. > If you have 100M-machine installed base, the probability of at least > one of them having a collision during this year will be 3*10-10. This > means that collisions will be happening in your installed base at the > rate of approximately once in 3 billion years. Substitute your own > numbers and repeat. > > Best wishes - > S.Osokine. > 24 Apr 2009. > > ________________________________ > > From: p2p-hackers-boun...@lists.zooko.com > [mailto:p2p-hackers-boun...@lists.zooko.com] On Behalf Of Russ Weeks > Sent: Thursday, April 23, 2009 11:54 PM > To: theory and practice of decentralized computer networks > Subject: [p2p-hackers] Probability analysis - any tips? > > > Hi, All. > > I'm playing around with building some data structures backed by a > conventional DHT like Chord or Kademlia. It seems like many of the elements > in these structures don't need a semantically useful key. Take a linked > list, for instance. I need to be able to do a "get" on the head or tail of > the list, but the keys of the interior elements don't need to be exposed to > the caller. This suggests that I can use random data for these keys. My > question is, what's the best way to generate these keys. > > The obvious approach is just to fill the key (say 128 bits) with random data. > I think I understand the birthday problem and how to estimate the > probability that a collision will occur. > > An alternative approach that was proposed to me was to use 64 bits of random > data and a 64-bit timestamp. Here, we hope that the random number generator > is not seeded with the system time. The theory is, the odds of generating 2 > identical 64-bit numbers in the same nanosecond is less than the odds of > generating 2 128-bit numbers over the lifetime of the system. If this is > true, it's not clear to me. > > Can anybody suggest a way to quantify the likelyhood of collision in the > second approach? > > Thanks, > > Russ > _______________________________________________ > p2p-hackers mailing list > p2p-hackers@lists.zooko.com > http://lists.zooko.com/mailman/listinfo/p2p-hackers > -- Bill McCormick _______________________________________________ p2p-hackers mailing list p2p-hackers@lists.zooko.com http://lists.zooko.com/mailman/listinfo/p2p-hackers
