4

I am struggling with the original paper trying to understand seemingly contradicting paragraphs. One example is where in 2.2 the authors declare that for bit space 160 there will be 160 k buckets, then later go on to say that in fact the buckets are a smaller number covering wider bit ranges and organized by prefix binary trees. In that 2.4 section they talk about unbalanced trees that lead to interpretations like the following, https://stackoverflow.com/a/32187456/442396 , where it is not clear if the answer there does reflect MMs intentions. Is there a clearly documented consensus out there that explains how these ambiguities should be interpreted in plain English?

Sentinel
  • 3,582
  • 1
  • 30
  • 44

1 Answers1

3

From David Mazières homepage [emphasis mine]:

Petar Maymounkov and David Mazières. Kademlia: A peer-to-peer information system based on the XOR metric. In Proceedings of the 1st International Workshop on Peer-to-Peer Systems (IPTPS '02), pages 53-65, March 2002. paper. (Short pre-proceedings version often cited, but please read the full paper, instead.)

Since the quoted links point to postscript here's the PDF of the full version

The sections beyond 2.2 in the longer 13-page version contain many enhancements and refinements which are not part of the original proof.

So the flat 160-bucket array can be seen as Kademlia 0.9 that was necessary for the basic proof while the tree-based version is Kademlia 1.0 which is necessary to implement those enhancements.

Note that the tree-based and flat approach are nearly equivalent if one does not implement any of the things in the later sections such as the unbalanced tree handling or bucket splitting.

Is there a clearly documented consensus out there that explains how these ambiguities should be interpreted in plain English?

Not that I am aware, but from the above I would argue that later sections simply trump earlier ones.

the8472
  • 40,999
  • 5
  • 70
  • 122
  • Man, I know saying thanks in comments is inappropriate but you just made my day. If I could send you a bottle of local bubbly I would. For interest it turns out that I might have been being overly pedantic about the whole thing anyway - a variant of the Kademlia protocol is used as part of the underlying P2P transport for Ethereum, which I am trying to get a detailed/technical handle on. In parallel with this analysis of M&M's Kademlia, I've since realized that the Kademlia variant is pretty loosely adopted in Ethereum and differs amongst client implementations..... – Sentinel Nov 27 '17 at 22:59
  • Yes, many real-world imlpementations of kademlia are quite sloppy and yet they still work. The key aspect that makes kademlia work reasonably efficient at internet scale is logarithmic locality organized into buckets. The rest is optimization, edge-cases and robustness. – the8472 Sep 03 '19 at 23:00
  • Thank you so much, this has been really helpful. Incase anyone is looking for the postscript it's here https://pdos.csail.mit.edu/~petar/pubs.html under the section "Graphs, flows, spectra and algorithms". – kimathie Jan 06 '21 at 10:10