Subject: Re: Val Henson's critique of hash-based content storage systems

From: Morten Welinder <[email-masked]>
Date: Fri, 29 Apr 2005 16:47:17 -0400

On 4/28/05, Rob Jellinghaus <[email-masked]> wrote:
> I assume most people here have read this, but just in case:
> 
> http://www.usenix.org/events/hotos03/tech/full_papers/henson/henson.pdf

The math in section 3 is bogus.  1-(1-2^-b)^n  isn't hard to compute and
even if it was, it is the wrong formula.  (Set n==2^b; you obviously should
get probability 1 for collision.)

The right formula is 1-B!/B^n/(B-n)! where B=2^n.  For n=2^80 and b=160
you get about 39%.

Morten