On Thu, Jul 06, 2006 at 04:11:17PM +0100, Jim Dixon wrote: > The second version of the paper has what appear to be serious internal > contradictions. In section 2.2, it says quite clearly that a k-bucket > contains a list of those nodes which are at a distance of [2^i .. 2^(i+1)) > from the current node, where node IDs are 160 bit quantities and the XOR > distance is a 160-bit big-endian quantity. In consequence, "for small > values of i, the k-buckets will generally be empty". Under this > interpretation, if the current node is in a k-bucket, it must be in bucket > zero. Bucket 127 will cover about half of all nodes, those for which the > high order bit of the node ID differs from that of the current node. > > Overall the picture is clear: there are 127 k-buckets, many of which > will be unoccupied, and a node will find its own node ID in bucket > 0, because the XOR distance between a node and itself is zero. There is > of course no reason at all to put its nodeID there and if node IDs are > distributed uniformly, it is exceedingly unlikely that bucket 0 will be > occupied at all, 2^-80.
Actually, there are 128 k-buckets, numbered 0 through 127. Bucket 0 could contain a peer with that has a differing lowest-order bit. Bucket 127 contains peers with differing highest-order bits. This is a very minor detail though... ;) > The account in section 2.4 seems quite different. "The routing table is > a binary tree whose nodes are k-buckets... Nodes in the routing > table are allocated dynamically as needed... Initially a node u's > routing tree has a single node, one k-bucket covering the entire ID > space." It goes on to describe how buckets are split when a node > is added. These are different ways of internally representing the same fundamental data. I suggest looking at my INFOCOM 2006 paper, which examines some variants of the basic Kademlia data structure, and includes some useful figures: http://www.barsoom.org/~agthorr/papers/infocom-2006-kad.pdf In particular, Figure 1(a) presents the basic Kademlia case, shown as a binary tree. Each internal node in the tree does not contain any contacts. If you fully instantiate the tree and store only the leaf nodes, then you have the 128 k-buckets. Representing it as a tree that grows on-demand is just a different way to represent the same abstract data structure. Which way the data is represented internally (a tree that grows on-demand vs. a fixed array) is up to the implementor. -- Daniel Stutzbach Computer Science Ph.D Student http://www.barsoom.org/~agthorr University of Oregon _______________________________________________ p2p-hackers mailing list [email protected] http://lists.zooko.com/mailman/listinfo/p2p-hackers
