[p2p-hackers] Sloppy Chord

Narayanan S RAMABHADRAN nramabha at cs.ucsd.edu
Mon Mar 31 12:59:03 UTC 2003


Hi

   This would probably work. However, to achieve theoretical guarantees,
it may be necessary to add a restriction, such as choosing a node with
uniform probability from that interval. If you choose based on a metric
like latency, you may not be able to theoretically show that it has the
same performance as Chord. In practice, it would probably do well. I have
done some as yet unpublished work that shows that choosing based on
uniform probability does indeed work well.

There is also some work from Stanford
called Symphony, published in USITS 2003, that does something similar.
They extend Chord by allowing a node to choose neighbors at random but
governed by a certain probability distribution over the key space that
ensures efficient routing. While this is not exactly "free choice", it
does loosen up some of the rigidity in Chord. It has the disadvantage that
you need to estimate N, the total number of nodes in the system.

   Regards,
   Sriram

   Narayanan Sriram Ramabhadran
   Graduate student
   Dept. of Computer Science & Engg.
   University of California San Diego


On Sun, 30 Mar 2003, Zooko wrote:

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