[p2p-hackers] Non-transitivity in DHTs

[Alen Peacock]

On 10/28/05, Michael J. Freedman <mfreed at cs.nyu.edu> wrote:
> Hi,
>
> At the risk of changing the active topic of DHTs and authentication, I
> wanted to point out a recent paper that we've just posted, which will
> appear at the upcoming WORLDS '05:
>
>    Non-Transitive Connectivity and DHTs
>    M. J. Freedman, K. Lakshminarayanan, S. Rhea, and I. Stoica
>    http://www.scs.stanford.edu/mfreed/docs/ntr-worlds05.pdf

Mike,

  This is a really nice paper, as it points out some problems that are
non-obvious to those of us in early stages of implementing DHTs
(without yet a lot of experience running them in large environments).

  For example, I've implemented a version of the Kademlia DHT based on
the original paper.  From your paper, I gather that I don't need to
worry about routing loops or broken return paths.  I do need to make
minor mods to deal with invisible nodes (unreachable cache and
eliminate blind trust).

  I'm not sure if I fully understand inconsistent roots as it relates
to kademlia.  Parallel iterative queries seem to make the probability
of getting an incorrect response from inconsistent roots less severe,
and implementing some sort of simple consensus easy -- since S directs
the routing process, it can compare the results from multiple
responses.  Does that seem right, or am I overlooking something more
essential to the problem?

  Alen