[IEEE P2P'11] Sub-Second Lookups on a Large-Scale Kademlia-Based Overlay


Previous studies of large-scale (multimillion node) Kademlia-based DHTs have shown poor performance, measured in seconds, in contrast to the far more optimistic results from theoretical analysis, simulations and testbeds.

BitTorrent DHT (MDHT), probably the largest DHT overlay on the Internet, many lookups already yield results in less than a second, albeit not consistently. With our backwards-compatible modifications, we show that not only can we reduce median latencies to between 100 and 200 ms, but also consistently achieve sub-second lookups.

These results suggest that it is possible to deploy latency- sensitive applications on top of large-scale DHT overlays on the Internet, contrary to what some might have concluded based on previous results reported in the literature.

Electronic Copy


  • R. Jimenez, F. Osmani, and B. Knutsson. "Sub-Second Lookups on a Large-Scale Kademlia-Based Overlay". 11th IEEE International Conference on Peer-to-Peer Computing 2011, Kyoto, Japan, Aug. 2011
  • @INPROCEEDINGS{jimenez2011subsecond,
    AUTHOR="Raul Jimenez and Flutra Osmani and Bjorn Knutsson",
    TITLE="{Sub-Second} Lookups on a {Large-Scale} {Kademlia-Based} Overlay",
    BOOKTITLE="11th IEEE International Conference on Peer-to-Peer Computing 2011 (P2P'11)",
    ADDRESS="Kyoto, Japan",



Data set

Please contact rauljc@kth.se


This work has been funded by the P2P-Next project.
Last changed: 2011-11-22