Hi Bill, The bucket splits are explained in the full proceedings version of the Kademlia paper:
http://www.scs.stanford.edu/~dm/home/papers/maymounkov:kademlia.ps.gz People very often refer to Kademlia by citing the pre-procedings version: http://www.scs.stanford.edu/~dm/home/papers/kpos.pdf Which misses a lot of details. Basically, bucket splits are very useful in order to make sure every node has the best knowledge of the contacts in the bucket containing its local node id. Additionally, in order to avoid the problem of highly unbalanced tree, a node can split a bucket that doesn't contain it's local node ID if that bucket is in the smallest subtree around the local bucket. Additionally, in the Mojito DHT implementation, we have a "symbol size" parameter (B), which defines the maximum depth of buckets in the tree. Therefore, when a bucket is full, we split it anyways if it's depth is smaller than B. Among other things, adding more buckets allows to improve a larger number of bits per lookup hops. In our implementation, this improvement is at least of B bits. Hope this helps. Cheers, Mark On 10/26/06, Bill Mccormick <[EMAIL PROTECTED]> wrote:
Hey Sam, This is really interesting, I didn't know the Limewire team was working on an open source DHT implementation. Something I noticed in both Mojito and the Azureus Kademlia implementations - when a Kademlia bucket is full, the implementation splits the bucket. This wasn't described in the original Kad paper (or anywhere else I've looked!). Do you know where I can find out what bucket splitting is all about? Bill On 10/26/06, Bill Mccormick <[EMAIL PROTECTED]> wrote: > > > ________________________________ > From: [EMAIL PROTECTED] > [mailto:[EMAIL PROTECTED] On Behalf Of > Sam Berlin > Sent: Wednesday, October 25, 2006 7:10 PM > To: theory and practice of decentralized computer networks > Subject: Re: [p2p-hackers] Cross-platform development > > > > > > >.and this is why java is realy just a corporate tool; though, LimeWire > did a good job; but they had to write some c-code as dll and wrap them with > java...so you'll really need to know java if you do that...or any other > emualted language for that matter. > > LimeWire really only uses C to do minor (mostly visual) tweaks. The entire > core is pure Java. Right now it's a little monolithic in terms of > architecture, but we're hoping to make the components more reusable in the > near future. (And the code is all GPL, so everyone else is welcome to do it > too.) The forthcoming Mojito DHT (Kademlia-based) will be a standalone Java > library that can plug in to any program. We already have some tests where > some programs are using Mojito tied into LimeWire and another is using it in > a stub-application, and both interoperate. > > Sam > > _______________________________________________ > p2p-hackers mailing list > [email protected] > http://lists.zooko.com/mailman/listinfo/p2p-hackers > > _______________________________________________ p2p-hackers mailing list [email protected] http://lists.zooko.com/mailman/listinfo/p2p-hackers
_______________________________________________ p2p-hackers mailing list [email protected] http://lists.zooko.com/mailman/listinfo/p2p-hackers
