[Gzz] Fwd: Re: [p2p-hackers] Sloppy Chord

[hemppah]

FYI.

Benja: What are our choices for implementing P2P ? Is it GISP/Khashmir (which
are variations of Kademlia) or Symphony, or..?

-Hermanni

----- Forwarded message from Narayanan S RAMABHADRAN <address@hidden> -----
    Date: Sun, 30 Mar 2003 18:29:15 -0800 (PST)
    From: Narayanan S RAMABHADRAN <address@hidden>
Reply-To: address@hidden
 Subject: Re: [p2p-hackers] Sloppy Chord
      To: address@hidden

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
> address@hidden
> http://zgp.org/mailman/listinfo/p2p-hackers
>

_______________________________________________
p2p-hackers mailing list
address@hidden
http://zgp.org/mailman/listinfo/p2p-hackers

----- End forwarded message -----




-------------------------------------------------
This mail sent through IMP: http://horde.org/imp/