<story><title>Some Useful Probability Facts for Systems Programming</title><url>https://theartofmachinery.com/2020/01/27/systems_programming_probability.html</url></story><parent_chain><item><author>fyp</author><text>Birthday paradox is way too important to omit from this list!&lt;p&gt;For example if you&amp;#x27;re uploading stuff to a bucket, you can compute its hash first to figure out if a duplicate already exists and if so, skip the upload.&lt;p&gt;Why can you do this? What if it was just a hash collision? Shouldn&amp;#x27;t you still compare the contents to &lt;i&gt;really&lt;/i&gt; make sure they are the same?&lt;p&gt;Turns out if your hash function is N bits you will need to have 2^(N&amp;#x2F;2) items before you see two hashed to the same thing by chance. If you choose a 256 bit cryptographic hash function like SHA256, that&amp;#x27;s 2^128. This probability is so low you have a higher chance of encountering a cosmic ray bit flip!&lt;p&gt;&lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Content-addressable_storage&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Content-addressable_storage&lt;/a&gt;&lt;p&gt;&lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Birthday_problem&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Birthday_problem&lt;/a&gt;</text></item></parent_chain><comment><author>SamBam</author><text>I don&amp;#x27;t quite understand how the birthday paradox relates to your example. Your example is how a hash collision is a very low probability event. But the birthday paradox is typically stated as odds being much &lt;i&gt;higher&lt;/i&gt; than you expect.&lt;p&gt;The hash collision problem is a birthday paradox, I suppose, but the probabilities are so low that that part isn&amp;#x27;t stressed in your post.&lt;p&gt;I feel like a better example of the Birthday Paradox would be something like:&lt;p&gt;I automatically give all my users a 5-character random ID. I figure there are nearly 12 million (26^5) combinations, so I should easily be able to support a hundred thousand users, since (naively) I calculate that the probability of the 1001st user matching any existing user is less than 1%. [1]&lt;p&gt;But if you calculate it correctly has the birthday paradox, you&amp;#x27;ll see that the probability of having a collision given 100,000 users is ~100%. [2]&lt;p&gt;[1] 1 - (1-(1&amp;#x2F;11881376))^100000 &amp;lt; 0.01&lt;p&gt;[2] 1 - (((11881376-1)&amp;#x2F;11881376)^((100000 * (100000-1))&amp;#x2F;2)) = 1</text></comment>
<story><title>Some Useful Probability Facts for Systems Programming</title><url>https://theartofmachinery.com/2020/01/27/systems_programming_probability.html</url></story><parent_chain><item><author>fyp</author><text>Birthday paradox is way too important to omit from this list!&lt;p&gt;For example if you&amp;#x27;re uploading stuff to a bucket, you can compute its hash first to figure out if a duplicate already exists and if so, skip the upload.&lt;p&gt;Why can you do this? What if it was just a hash collision? Shouldn&amp;#x27;t you still compare the contents to &lt;i&gt;really&lt;/i&gt; make sure they are the same?&lt;p&gt;Turns out if your hash function is N bits you will need to have 2^(N&amp;#x2F;2) items before you see two hashed to the same thing by chance. If you choose a 256 bit cryptographic hash function like SHA256, that&amp;#x27;s 2^128. This probability is so low you have a higher chance of encountering a cosmic ray bit flip!&lt;p&gt;&lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Content-addressable_storage&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Content-addressable_storage&lt;/a&gt;&lt;p&gt;&lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Birthday_problem&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Birthday_problem&lt;/a&gt;</text></item></parent_chain><comment><author>jerf</author><text>&amp;quot;This probability is so low you have a higher chance of encountering a cosmic ray bit flip!&amp;quot;&lt;p&gt;We commonly conceive of our computers as 100% accurate, but as you observe here, for this and other reasons they aren&amp;#x27;t. The distribution of errors is exceedingly pathological; the vast majority of errors you will encounter are not independent but are highly correlated, because some particular bit of hardware is flawed in some manner.&lt;p&gt;Ignore those for a moment, and consider just the purely-random failures, like cosmic or thermal bit flips. The rate on these is still non-zero. Very small, but high enough that we&amp;#x27;ve pretty much all encountered them, usually without realizing it. (While it is true that a single bit flip can bring a program down if it is the correct bit, the &lt;i&gt;average&lt;/i&gt; bit flip will have no visible manifestation of any kind.)&lt;p&gt;This creates a &amp;quot;noise floor&amp;quot; for our computations. Any event which has a probability lower than this &amp;quot;noise floor&amp;quot; for happening can be treated as the same zero probability you treat the possibility of totally random hardware failure.&lt;p&gt;The probably of two random pieces of content having the same SHA256 hash by random chance is in practice zero, and you may write your code that way. The potential problem that one may wish to defend against is the possibility that two pieces of content have the same SHA256 hash for &lt;i&gt;non-&lt;/i&gt;random reasons, which is to say, the possibility that it will be broken. But the defense against that is rather different. There&amp;#x27;s a lot of nasty possibilities that lie above this noise floor that still need to be dealt with.&lt;p&gt;I have seen this concept kinda bothers people sometimes. But you are justified in just ignoring anything below this noise floor. There&amp;#x27;s basically never a reason to worry about this noise floor, because once you understand what it really means, you will see you lack to the tools to deal with it. Given an error, the probability that the error is the result of some non-random systemic issue is much higher than the probability that it was a truly random error. Even if you care about reliability a lot, like in space or medicine, the problem you need to deal with is failing hardware. If you try to write code to deal with the noise floor, it is much more likely to be getting invoked due to systemic, non-random issues... after all, a &amp;quot;low probability&amp;quot; failure on a network link that corrupts one packet a day is still &lt;i&gt;multiple orders of magnitude&lt;/i&gt; above this noise floor.</text></comment>