[p2p-hackers] Non-transitivity in DHTs

[Michael J. Freedman]

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

While DHT algorithms seem quite elegant on paper, in practice we found 
that a great deal of our implementation effort was spent discovering and 
fixing problems caused by non-transitivity. Of course, maintaining a full 
link-state routing table at each DHT node would have sufficed to solve all 
such problems, but would also require considerably more bandwidth than a 
basic DHT. Instead, we each independently discovered a set of "hacks" to 
cover up the false assumption of full connectivity on which DHTs are 
based.

Collectively, the authors have produced three independent DHT 
implementations: the Bamboo implementation in OpenDHT, the Chord 
implementation in i3, and the Kademlia implementation in Coral. 
Moreover, we have run public deployments of these three DHTs on PlanetLab 
for over a year.

In this paper, we categorize the ways in which Bamboo, Chord, and Kademlia 
break down under non-transitivity, and we enumerate the ways we modified 
them to cope with these shortcomings.  We also discuss application-level 
solutions to the problem.  Many of these failure modes and fixes were 
quite painful for us to discover, and we hope that-at least in the short 
term-this work will save others the effort.  In the longer term, we hope 
that by focusing attention on the problem, we will encourage future DHT 
designers to tackle non-transitivity head-on.

-----

Beyond communicating these details to the development community, we had 
hoped to engender further discussion on how other DHT designers and 
implementors have dealt with similar problems and on what techniques 
should be used to avoid such limitations in the future.

Thanks,
--mike


-----
www.michaelfreedman.org                              www.coralcdn.org