[p2p-hackers] Sloppy Chord

Zooko zooko at zooko.com
Sun Mar 30 12:53:02 UTC 2003


A fundamental advantage of Pastry [1] and Kademlia [2] over Chord [3] would seem 
to be that in the former two, there is a "free choice" in which peers a node 
links to, whereas in Chord each peer is uniquely determined.

The Pastry papers describe this feature in terms of an arbitrary "proximity 
metric".  The Kademlia paper says:

"Worse yet, asymmetry leads to rigid routing tables.  Each entry in a Chord 
 node's finger table must store the precise node preceding some interval in the 
 ID space.  Any node actually in the interval would be too far from nodes 
 preceding it in the same interval.  Kademlia, in contast, can send a query to 
 any node within an interval, ..."

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.

But is this rigidity really a consequence of Chord's asymmetric distance metric?

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".

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.

Regards,

Zooko

[1] http://citeseer.nj.nec.com/rowstron01pastry.html
[2] http://citeseer.nj.nec.com/529075.html
[3] http://citeseer.nj.nec.com/stoica01chord.html

http://zooko.com/
         ^-- under re-construction: some new stuff, some broken links



More information about the P2p-hackers mailing list