[p2p-hackers] Sloppy Chord

Gordon Mohr gojomo at usa.net
Sun Mar 30 18:56:02 UTC 2003


You've probably seen the IPTPS03 paper, "Sloppy Hashing and Self-Organized
Clusters", by David Mazieres and Michael Freedman:

   http://iptps03.cs.berkeley.edu/final-papers/coral.pdf

I suspect many of the strict Chord (and other DHT) assumptions can be 
loosened while still achieving excellent, nearly equivalent performance -- 
though it then becomes harder to rigorously prove such performance. 

- Gordon
  
----- Original Message ----- 
From: "Zooko" <zooko at zooko.com>
To: <p2p-hackers at zgp.org>
Sent: Sunday, March 30, 2003 12:51 PM
Subject: [p2p-hackers] Sloppy Chord


> 
> 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
> _______________________________________________
> p2p-hackers mailing list
> p2p-hackers at zgp.org
> http://zgp.org/mailman/listinfo/p2p-hackers



More information about the P2p-hackers mailing list