[p2p-hackers] Re: Opaque Key Access in DHT's ??

John Casey john.casey at gmail.com
Wed Dec 1 07:49:09 UTC 2004


Thanks paul. That has helped a lot. Sorry for the late reply but I
thought all messages where going to the mailing list. I have re: cc'd
your reply to the mailing list.

On Wed, 3 Nov 2004 17:28:34 -0800, Paul Campbell <paul at ref.nmedia.net> wrote:
> First off, there's nothing that says you can't route/search a "region" of
> DHT space. Look at the various DHT-based broadcast protocols.
> Essentially, a broadcast protocol sends a message routed via the DHT
> that consists of "send(lowID, highID)".
> On receipt by a node in the range, in order to implement broadcasting, the
> node then forwards the message on to neighbors that cover any subranges not
> covered by the receiving node, changing the lowID/highID ranges appropriately.
> A search would be something like:
> broadcast(fromID, "keylow", "keyhigh")
> Second, Bloom filters can summarize any number of items. The key is that the
> false positive rate of the filter increases as the number of items increases.
> So you can potentially summarize as many items as you want, but the false
> positive rate will increase dramatically once you get somewhat beyond the
> "capacity" of a particular Bloom filter. In order to reduce this problem,
> either the number of bits in the filter has to be increased or the number of
> items has to be decreased.
> There are a bunch of potential tuning parameters in Bloom filters (number of
> hashes, compression details if compression is used), but eventually the
> fundamental Shannon information rate starts to become a serious limiting
> factor.

More information about the P2p-hackers mailing list