[p2p-hackers] Errata in the Chord paper ?

[Bryan Turner]

Mike,

	That's a very succinct way of describing it, thanks for the input!

Bibliography:
-------------

Vivaldi: A Decentralized Network Coordinate System
Frank Dabek, Russ Cox, Frans Kaashoek, Robert Morris
http://pdos.csail.mit.edu/~rtm/papers/p426-dabek.pdf

	This is an updated version of the original Vivaldi paper.  If you
read the first one, read this one too!

Novel Architectures for P2P Applications: The Continuous Discrete Approach
Moni Naor, Udi Wieder
http://www.wisdom.weizmann.ac.il/~naor/PAPERS/dh.pdf

	My preferred DHT construction.  Very flexible, stable, and simple.
Ignore sections 2.2-2.4, 3, 4.1, 5.2 and 6.  Pay particular attention to
section 5.1.  Chord is a restricted 1-dimensional instance of this
construction.  Also look up their other P2P papers, all very good ideas.

Kademlia: A Peer-to-peer Information System Based on the XOR Metric
Petar Maymounkov, David Mazieres
http://citeseer.ist.psu.edu/529075.html

	An almost trivial extension to Chord that solves some of the
problems I mentioned.  Forego the XOR metric, it is actually irrelevant to
the paper's results and causes some pedagogical head-scratching when trying
to work out the path of queries.

Symphony: Distributed Hashing in a Small World
Gyrneet Singh Manku, Mayank Bawa, Prabhakar Raghavan
http://citeseer.ist.psu.edu/manku03symphony.html

	I recalled incorrectly, it was this paper that had the suggestions
for Chord, not the Kademlia paper.  An overview of Small World network
construction, with some useful results and applications to other networks.
See comments for Chord in section 5.4(b).

--Bryan
bryan.turner at pobox.com

-----Original Message-----
From: p2p-hackers-bounces at zgp.org [mailto:p2p-hackers-bounces at zgp.org] On
Behalf Of Michael Parker
Sent: Monday, September 26, 2005 2:26 PM
To: p2p-hackers at zgp.org
Subject: RE: [p2p-hackers] Errata in the Chord paper ?

Just to chime in quickly on the single point below... In Chord, you can
easily do away with the rigidity by allowing the first finger to point to
any node in the range [2^159, 2^160), not just the first node encountered
clockwise in this range. Likewise, the second finger can point to any node
in the range [2^158, 2^159), and so forth. This affords you much greater
flexibility for choosing neighbors (indeed, your farthest finger can be
chosen from approximately half the nodes on the network), allowing you to
exploit some sort of proximity metric such as Vivaldi in neighbor selection.
The average number of hops when routing a message still remains (log N)/2.
See the paper "The Impact of DHT Routing Geometry on Resilience and
Proximity" by Gummadi et al for a more detailed discussion on this.

Everything else Bryan says is good advice :)

- Mike Parker


Quoting Bryan Turner <bryan.turner at pobox.com>:

> - Too Rigid
>
> 	Chord specifies that you must maintain exact successor/predecessor 
> and finger tables at all times.  This requirement causes a significant 
> amount of network overhead during network flapping events, and at 
> times of the day when large swings in population occur.  Often, this 
> traffic is enough to destabilize the network and cause routing to fail.
>
> 	Chord is one of many algorithms to build a Small World network.  It 
> has been shown that perfectly aligned finger tables are not necessary 
> (as some of their later papers mention).  Instead, keep tabs on your 
> local neighborhood and keep "some" long-range pointers for efficient
routing.
>
> 	Specifically, your long range pointers should connect to well 
> established, well connected, well trusted nodes at various distant 
> locations on the ring.

_______________________________________________
p2p-hackers mailing list
p2p-hackers at zgp.org
http://zgp.org/mailman/listinfo/p2p-hackers
_______________________________________________
Here is a web page listing P2P Conferences:
http://www.neurogrid.net/twiki/bin/view/Main/PeerToPeerConferences