[p2p-hackers] Sloppy Chord

Brandon Wiley blanu at bozonics.com
Mon Mar 31 12:55:03 UTC 2003

> This feature seems very important to me, not because the "free choice" part can 
> be used to select peers with low latency or few network hops, but because it can 
> be used to select on arbitrary other criteria, such as avoiding peers that are 
> unreachable (due to an incompletely connected underlying network), avoiding 
> peers that are untrusted, or other criteria.

Some of this you could do with MIT Chord. If a node has a globally known
property (unreachability, untrustedness according to a central authority)
then you can just not let "bad" nodes join. You only need "sloppy" Chord
if you want nodes to make a routing choice which is based on subjective
criteria or information.

One of my censorship resistance schemes for China works like the former.
The global criteria for joining is that the node is not in China
(according to a ip->location service). This forms a supernode-like network
of "good" (not in China) nodes with the "bad" (in China) nodes attached
to the edges of the network. Unlike other supernode-based networks like
Kazaa, however, the supernodes are not organzed haphazardly, but into a
nice, neat Chord ring.

I also do this for the Alluvium mirror-finding network by having the
criteria be "not behind NAT".

> Brandon Wiley suggested to me that one could have a "Sloppy Chord", using the 
> same, asymmetric, distance metric, but changing the requirement of the k'th 
> finger table entry from "the precessor of selfId + 2^k" to "a node in the 
> interval 2^(k-1) through 2^k".

On important thing to remember about Chord is that for the lookups to
succeed, you *only* need for next pointers to be correct and to always
follow pointers forward. You don't need finger tables. You can have
incorrect finger tables as long as you never follow a bad finger
backwards, and this is something you can easily check for yourself.

MIT Chord sets you up with a finger table which you can follow for the
nice O(log N). However, you should feel perfectly free to keep around
references to nodes that don't fit in your finger table. And you should
feel free to follow such references if they are closer to the key than
either 1) you or 2) the last reference you followed, and 3) you like them
better than the other references you have by some criteria.

I can't guarantee that if you follow references other than your finger
table you'll get there in O(log n). However, you can't optimize for two
things at once. If you want to get there fast, the finger table is your
roadmap to guaranteed speed. Of course some reference you have might
actually be closer to the key than your finger table's reference. Then you
should follow that. The O is the same, but the actual time to the key
might be less. If you don't care about getting there as fast as possible,
use something based on criteria other than being in your finger table.
You'll still get there for sure.

> After thinking about it for a few minutes, there isn't any obvious reason why 
> this wouldn't have the same asymptotic performance guarantees as proper MIT 
> Chord.

I wish there was some analysis on this. I can only say that I don't see a
problem here, but I don't feel like trying to prove it. Of course, this is
one of the non-technical problems with MIT Chord. It sticks very closely
to the provable whereas for real applications less provable systems with
better actual properties are desirable.

More information about the P2p-hackers mailing list