Kademlia is a protocol for building a distributed hash table (DHT), which is a fancy way of saying that it's a method for a network to communicate and store data efficiently without a central server. Invented in 2002, Kademlia has been the basis of a number of systems. Lately DHTs in general, and Kademlia in particular, have received a lot of attention from decentralized web projects. In fact, Kademlia forms the basis of a number of interesting projects, including OpenBazaar, MaidSafe, and Storj.
The goal of any DHT is to store data on a network full of people you don't know, and then be able to find it later. Computers on the network are called nodes. We usually think of the network as a giant interconnected graph full of nodes. These nodes communicate according to certain rules. Kademlia is one set of rules that seems to work pretty well. Following these rules keeps the number of messages sent low, and makes it very likely you can find what you're looking for in a reasonable amount of time.
Kademlia works a bit like an old-school phone tree. When I want to communicate, retrieve, or store something, I phone my friends to let them know. They can either help or at least will know someone who might be able to help. I can keep phoning people until I find the right person for the job. Kademlia has rules for how to phone someone, what to say to them, how to find the right place to store something, and even who my friends should be. Many of these rules are based on a concept called "distance."
Distance and Color
If we want to find people and data in a giant sea of nodes, we need to have a concept of where things "should" go. In Kademlia we base this on distance. Nodes should talk more to nodes that are close to them. To define distance, Kademlia requires each node and each piece of data to have an ID. Data IDs are called "keys" and the data itself is a "value." Together they form a key-value pair.
If I wanted to run Kademlia with real people, I'd get a few thousand people together and have everyone bring their own brightly-colored t-shirt (a node ID). Colors are obvious, it's easy to see the difference between purple, green, and red, and there are enough shades that everyone can have a different color. At first everyone talks randomly and tries to find and stand with people with similar shirts. Over time all the blues will clump to one area, and all the purples to a nearby area, with a smooth gradient from blue to purple in the middle.
Once everyone's found their place, people wearing blue will naturally talk a lot to people wearing blue. They're nearby, after all. But they'll still have a few friends in purple, red, orange, and all the other colors. Then if a blue shirt wants to talk to a specific orange shirt, they can call their orange friend, who will connect them to the person wearing the right shade of orange, or at least point them in the right direction.
The point of Kademlia is to store key-value pairs. Let's say I have a shiny red apple I'd like to save for later. I'll take a close look at my apple (the value), and take a picture so I have a record of its exact color (the key). Then I'll show it to my friend in a red shirt. She's not exactly the right shade, but she's the closest that I know. She'll look at the apple, look at all her red friends, and introduce me to the person wearing the shirt whose color is closest to the apple's color. We might have to go through this process of color evaluation and introduction several times. Once I stop getting introduced to people (which means I've found the guy whose shirt is closest to apple-red), I'll toss him the apple, and tell him to have a nice day.
Periodically throughout the day, everyone checks their pockets, and makes sure they're still the right person to hold the things they have. If they have a new friend with a more apple-y shirt, they might pass my apple on to that person for safekeeping. The goal is to have everything as close as possible to its color at all times, so that when someone comes looking for it, they can find it by matching shirt color (node ID) to object color (key).
Later, when I want to eat my apple, I'll look through my address book, and see who I know with a really apple-y red shirt, and show him the picture. He might have the apple, but if he doesn't, he'll look around, and see which of his red-shirted friends matches that color most closely. Once he finds a likely person, he'll introduce us. The process repeats, searching through the network of red shirts, guided only by the color I'm seeking. Once I get introduced to the guy with the apple, he'll hand it over, and I'll give him a hug for being such a cool guy.
The person holding the apple doesn’t need to know anything about me to hold on to that apple for me. This is a great feature of the network because it means that if I want to let someone else have my apple, I can just give them the photo. Using the photo they can go through the whole apple-finding process the same way. The color (the key) can always be used to find the apple (the value), regardless of who’s looking. They’ll ask different people than me at first, but as they get closer to the apple their route will converge with mine. The method of searching naturally channels the searcher to the value.
XOR
Instead of using color, Kademlia uses long binary numbers. And instead of eyeballing shade differences, Kademlia uses a logical operator called "exclusive or" or "XOR." XOR is an binary measure of dissimilarity. It takes two numbers, goes through each digit, and outputs which digits are different. This output is used as the distance between those nodes, or the distance between that node and that key. Because XOR distance is easy to measure and compare, data can quickly and efficiently find its home in the network, and nodes can find the thing they're looking for easily, if it's out there.
XOR has a few interesting properties that make it very useful for a network like Kademlia. It's fast, efficient, and well-understood, meaning any node can use it, even fairly low-power ones. But more importantly, it translates the physical concept of distance to a digital space very well. My XOR distance to myself is always exactly 0, meaning I am a stationary point of reference. Just like a negative distance is non-sensical in real life, XOR will never give a negative output. It's symmetric, meaning that my distance to Alice is always the same as Alice's distance to me. And because the output is unique for a given input, there can never be two nodes exactly the same distance from me.
These properties create a network where every node falls into place naturally. While nodes are following the rules (and even when some of them aren't) all their actions and messages conspire to create a beautiful and useful network. Order is not assigned by a central server, or created by a hierarchy of authority, but flows from the protocol itself. That's what makes it so interesting to decentralized projects: it demonstrates that useful cooperation can be achieved by intelligent creation of a protocol, rather than building something chaotic and imposing order on it later.
Further reading:
One of my friends at MaidSafe wrote a technical explanation of XOR distance over here. I would highly recommend it for a more in-depth look at how all this works in practice.