[p2p-hackers] Sloppy Chord
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:
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.
----- 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  and Kademlia  over Chord  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
>  http://citeseer.nj.nec.com/rowstron01pastry.html
>  http://citeseer.nj.nec.com/529075.html
>  http://citeseer.nj.nec.com/stoica01chord.html
> ^-- under re-construction: some new stuff, some broken links
> p2p-hackers mailing list
> p2p-hackers at zgp.org
More information about the P2p-hackers