Hello, I'm Maneshwar. I'm building git-lrc, a Micro AI code reviewer that runs on every commit. It is free and source-available on Github. Star git-lrc to help devs discover the project. Do give it a try and share your feedback. Yesterday we understood XOR distance, that weird little metric that has nothing to do with geography but somehow behaves exactly like a distance is supposed to.
If you haven't read it, quick recap: XOR two IDs, read the result as a number, that's your distance, and it satisfies zero-self-distance, symmetry, and the triangle inequality.
{% embed https://dev.to/lovestaco/bitwise-and-otherwise-understanding-xor-distance-1kh8 %}
So today we look at the thing that actually uses that math to build a real, working, decentralized network: Kademlia.
It's the DHT (distributed hash table) algorithm quietly running under BitTorrent, IPFS, Ethereum's peer discovery, and Ethereum Swarm's storage layer.
Thousands of peers join and leave whenever they feel like it, and you need to answer one question fast: "who has the thing I'm looking for?"
The obvious approaches all fall apart: Ask everyone. Congrats, you've built a broadcast storm generator, not a network. Keep a central index. That's just a server with extra steps, and now you have a single point of failure and the "decentralized" label is a lie. Every node remembers every other node. Works fine until you have a million nodes and your "lightweight P2P client" needs a gigabyte of RAM just for contacts.
Kademlia's pitch is simple to state and genuinely clever to pull off: every node only needs to remember a small, logarithmic number of peers, and it can still find anything in the network in a logarithmic number of hops.
Each node keeps a routing table split into "buckets," where bucket i holds peers whose XOR distance falls in the range 2^i, 2^(i+1)).
In plain English: bucket 0 holds peers that differ from you in only the very last bit, and the highest bucket holds peers that barely share anything with your ID at all.
Kademlia trusts old, still-responsive peers over shiny new ones, because nodes that have been around a while are statistically more likely to keep being around.
Notice the asymmetry: low buckets cover a tiny slice of ID space so there aren't many peers that could even qualify, and you know them intimately.
High buckets cover a massive slice of ID space, so you just keep a small sample instead of trying to know everyone out there.
Kademlia asks alpha peers in parallel (usually 3), and keeps looping: ask your current best guesses for who they know that's even closer, fold the new answers in, repeat, until nobody can suggest anyone closer.
Because of the triangle inequality we talked about yesterday, this loop is guaranteed to make monotonic progress.
Typically this converges in about O(log n) hops for a network of n nodes, which is the whole reason this scales to millions of peers without falling over.
Here's the fun part. The same core algorithm shows up wearing very different outfits: BitTorrent's Mainline DHT ([BEP 5) uses it so torrents can find peers without needing a central tracker. IPFS / libp2p (spec here) uses it to find which peers on the network are hosting a given content-addressed piece of data. Ethereum's discv5 (spec here) uses it purely for peer discovery, finding other Ethereum nodes to connect to.
The Ethereum Swarm twist is worth dwelling on for a second because it's genuinely different from vanilla Kademlia.