From: Morten Welinder <mwelinder@gmail.com>
Date: Fri, 29 Apr 2005 20:47:17 GMT
Subject: Re: Val Henson's critique of hash-based content storage systems
Message-ID: <118833cc0504291347ea1a3fa@mail.gmail.com>
In-Reply-To: <loom.20050429T015434-928@post.gmane.org>

On 4/28/05, Rob Jellinghaus <robj@unrealities.com> 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