.. DO NOT EDIT. .. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY. .. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE: .. "api/gallery/network/overlays/plot_01_kademlia.py" .. LINE NUMBERS ARE GIVEN BELOW. .. only:: html .. note:: :class: sphx-glr-download-link-note :ref:`Go to the end ` to download the full example code or to run this example in your browser via JupyterLite. .. rst-class:: sphx-glr-example-title .. _sphx_glr_api_gallery_network_overlays_plot_01_kademlia.py: Kademlia: routing by XOR distance (Maymounkov and Mazières 2002) ================================================================ A distributed hash table stores each key at the nodes whose identifiers are closest to it, and lets any node find them without a central index. Kademlia measures closeness as the XOR of two identifiers. Each node keeps a *k-bucket* of contacts at every distance scale: a few nodes that share none of its leading bits, a few that share exactly one, and so on. Every hop toward a key at least fixes the next differing bit, so a lookup among n nodes takes about ``log2 n`` hops at most and far fewer on average. Ethereum's discovery protocol and IPFS use Kademlia. What to look for ---------------- Every lookup ends at the true closest node. The number of hops grows by a constant each time n quadruples: logarithmic growth, a straight line on a log axis. Larger buckets mean fewer hops, at the price of bigger tables. The history behind this experiment: :doc:`/history/network_breakthroughs`. .. GENERATED FROM PYTHON SOURCE LINES 25-27 Build networks of 64 to 4096 nodes ---------------------------------- .. GENERATED FROM PYTHON SOURCE LINES 27-52 .. code-block:: Python from random import Random import matplotlib.pyplot as plt import numpy as np import blockchainkit as bk random = Random(1) sizes = [64, 256, 1024, 4096] mean_hops = {1: [], 4: []} for n in sizes: ids = random.sample(range(2**32), n) for k in mean_hops: network = bk.network.KademliaNetwork(ids, bits=32, k=k, seed=1) hops = [] for _ in range(200): target = random.randrange(2**32) result = network.lookup(random.choice(ids), target) assert result.found == network.closest(target, 1)[0] hops.append(result.hops) mean_hops[k].append(np.mean(hops)) print({k: [round(float(h), 2) for h in v] for k, v in mean_hops.items()}) steps = np.diff(mean_hops[1]) assert all(0.4 < step < 1.6 for step in steps) # About one more hop per quadrupling. .. rst-class:: sphx-glr-script-out .. code-block:: none {1: [2.91, 3.81, 4.79, 5.93], 4: [1.7, 2.23, 2.88, 3.4]} .. GENERATED FROM PYTHON SOURCE LINES 53-56 One lookup, bit by bit ---------------------- Each hop shares a longer prefix with the target. .. GENERATED FROM PYTHON SOURCE LINES 56-69 .. code-block:: Python network = bk.network.KademliaNetwork(ids, bits=32, k=1, seed=1) target = 0xDEADBEEF for node in network.lookup(ids[0], target).path: shared = 32 - bk.network.xor_distance(node, target).bit_length() print(f"{node:032b} shares {shared:2d} leading bits") fig, ax = plt.subplots(figsize=(6, 4)) for k, hops in mean_hops.items(): ax.semilogx(sizes, hops, "o-", base=2, label=f"k = {k}") ax.set(xlabel="nodes n", ylabel="mean hops", title="Lookups take O(log n) hops") ax.legend() fig.tight_layout() .. image-sg:: /api/gallery/network/overlays/images/sphx_glr_plot_01_kademlia_001.png :alt: Lookups take O(log n) hops :srcset: /api/gallery/network/overlays/images/sphx_glr_plot_01_kademlia_001.png :class: sphx-glr-single-img .. rst-class:: sphx-glr-script-out .. code-block:: none 11101000111001111111010001001101 shares 2 leading bits 11000010111100000000101000010111 shares 3 leading bits 11010110001011101010100011011001 shares 4 leading bits 11011011100000111100110100100111 shares 5 leading bits 11011100100100110100000100111010 shares 6 leading bits 11011110011000100111111001010110 shares 8 leading bits 11011110101101011111001111100001 shares 11 leading bits 11011110101011000111001110111001 shares 15 leading bits .. GENERATED FROM PYTHON SOURCE LINES 70-75 Exercise -------- Real Kademlia queries ``alpha = 3`` contacts in parallel and keeps the ``k`` closest it has heard of. Why does that make a lookup robust when some contacts are offline, and how would you count its hops? .. rst-class:: sphx-glr-timing **Total running time of the script:** (0 minutes 6.209 seconds) .. _sphx_glr_download_api_gallery_network_overlays_plot_01_kademlia.py: .. only:: html .. container:: sphx-glr-footer sphx-glr-footer-example .. container:: lite-badge .. image:: images/jupyterlite_badge_logo.svg :target: ../../../../lite/lab/index.html?path=api/gallery/network/overlays/plot_01_kademlia.ipynb :alt: Launch JupyterLite :width: 150 px .. container:: sphx-glr-download sphx-glr-download-jupyter :download:`Download Jupyter notebook: plot_01_kademlia.ipynb ` .. container:: sphx-glr-download sphx-glr-download-python :download:`Download Python source code: plot_01_kademlia.py ` .. container:: sphx-glr-download sphx-glr-download-zip :download:`Download zipped: plot_01_kademlia.zip ` .. only:: html .. rst-class:: sphx-glr-signature `Gallery generated by Sphinx-Gallery `_