git/list[1] front-page[2] threads[3] people[4] search[5] about
 

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

From
MWMorten Welinder <mwelinder@gmail.com>
Date
Apr 29, 2005, 20:47 UTC
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
Previous: H. Peter Anvin
Message 8 of 8 in “Val Henson's critique of hash-based content storage systems”
  1. Rob JellinghausApr 29, 2005
  2. Linus TorvaldsApr 29, 2005
  3. Tom LordApr 29, 2005
  4. C. Scott AnanianApr 29, 2005
  5. Tom LordApr 29, 2005
  6. C. Scott AnanianApr 29, 2005
  7. H. Peter AnvinApr 29, 2005
  8. Morten WelinderApr 29, 2005

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.