System Details
The first generation peer-to-peer file sharing networks, such as Napster, relied on a central database to co-ordinate look ups on the network. Second generation peer-to-peer networks, such as Gnutella, used flooding to locate files, searching every node on the network. Third generation peer-to-peer networks use Distributed hash tables to look up files in the network. Distributed hash tables store resource locations throughout the network. A major criterion for these protocols is locating the desired nodes quickly.
Kademlia uses a "distance" calculation between two nodes. This distance is computed as the exclusive or of the two node IDs, taking the result as an integer number. Keys and Node IDs have the same format and length, so distance can be calculated among them in exactly the same way. The node ID is typically a large random number that is chosen with the goal of being unique for a particular node (see UUID). It can and does happen that geographically widely separated nodes—from Germany and Australia, for instance—can be "neighbors" if they have chosen similar random node IDs.
Exclusive Or was chosen because it shares some properties with the geometric distance formula. Specifically:
- the distance between a node and itself is zero
- it is symmetric: the "distance" calculated from A to B and from B to A are the same
- it follows the triangle inequality: given A, B and C are vertices(points) of a triangle, then the distance from A to B is shorter than (or equal to) the sum of the distance from A to C to B.
These properties provide most of the important behaviors of measuring a real distance with a significantly lower amount of computation to calculate it.
Each Kademlia search iteration comes one bit closer to the target. A basic Kademlia network with 2n nodes will only take n steps (in the worst case) to find that node.
Read more about this topic: Kademlia
Famous quotes containing the words system and/or details:
“It is not easy to construct by mere scientific synthesis a foolproof system which will lead our children in a desired direction and avoid an undesirable one. Obviously, good can come only from a continuing interplay between that which we, as students, are gradually learning and that which we believe in, as people.”
—Erik H. Erikson (20th century)
“If my sons are to become the kind of men our daughters would be pleased to live among, attention to domestic details is critical. The hostilities that arise over housework...are crushing the daughters of my generation....Change takes time, but men’s continued obliviousness to home responsibilities is causing women everywhere to expire of trivialities.”
—Mary Kay Blakely (20th century)