Re: distributed hash tables

[Erik Nordmark <Erik.Nordmark@sun.com>]

> If you can distribute your information over a set of reliable and 
> trustworthy nodes, this could work very well. However, we can't assume 
> any one node to be reliable, so we need to build in a good deal of 
> redundancy and dynamic replication. This also means that a resolver may 
> need to contact several nodes in sequence to find the required 
> information. But it gets worse: a node that is supposed to hold a 
> certain piece of information could, rather than hand over the requested 
> information, claim that the information doesn't exist. The only way 
> that I can see to get around this is distribute copies of the same 
> piece of information over so many nodes that it becomes infeasible to 
> corrupt them all. Which probably means there isn't a workable tradeoff 
> between security/reliability and performance.
> 
> So essentially this has all the downsides of DNS and then some, with 
> the only advantage that you now get to search in flat spaces too.

I guess we don't agree on the parameters of the problem we are trying to
solve yet.

One possible set of parameters is that the identifier space is hierarchically
structured with "sufficient" hierarchy. In such a case a hierarchical lookup
system like the DNS might be appropriate.

Another possible set of parameters is that the identifier space is flat
(for example, an ID is based on a hash of a public key) or with limited
hiearchy (e.g., N bits of flat site ID followed by 128-N bits of flat
"ID within site"). In that case a hierarchical lookup system like the DNS
doesn't seem like a good fit.

Figuring out how to use a DHT in the latter case has some issues that folks
need to look at. In addition to the ones you pointed out, one would also
need to be able to do DHT resolution for nodes belonging to the same site
when the site is cut off from the rest of the internet.

  Erik