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

[hemppah]

Hi,

It seems to be that the advantages of Kademlia and Sloppy hashing are noticed by
others, too ;).

-Hermanni



----- Forwarded message from Gordon Mohr <address@hidden> -----
    Date: Sun, 30 Mar 2003 18:55:21 -0800
    From: Gordon Mohr <address@hidden>
Reply-To: address@hidden
 Subject: Re: [p2p-hackers] Sloppy Chord
      To: address@hidden

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" <address@hidden>
To: <address@hidden>
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
> 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/