networksimulator at gmail.com
Wed Mar 8 06:08:20 UTC 2006
Well... Small-world is characterized by both a high clustering degree =
short average path length. While DHTs are designed to have short paths =
node to node, they do not necessarily present clustering.=20
I just thought about Chord... The nodes keep track of neighbors every =
steps away. I don't think the nodes are clustering here, or am I wrong
=B7=A2=BC=FE=C8=CB: p2p-hackers-bounces at zgp.org =
[mailto:p2p-hackers-bounces at zgp.org] =B4=FA
=B1=ED Daniel Stutzbach
=B7=A2=CB=CD=CA=B1=BC=E4: 2006=C4=EA3=D4=C28=C8=D5 12:56
=CA=D5=BC=FE=C8=CB: p2p-hackers at zgp.org
=D6=F7=CC=E2: Re: [p2p-hackers] clustering
On Tue, Mar 07, 2006 at 07:43:39PM -0800, Gary Jefferson wrote:
> Just a general question for the list: DHTs don't exhibit small-world=20
> characteristics, at least not in the overlay network view of things,=20
> right? I mean, from each node's perspective, it might look a bit like =
> a small world -- in Kademlia, for instance, my routing tables will=20
> center around my own ID space.
DHTs typically are small worlds.
The small-world characteristics are short path lengths (comparable to a
random graph) and high clustering (much more than a random graph).
DHTs certainly have short path lengths (that's the point). All the DHTs =
can think of also have high clustering. A node's neighbors are likely =
also be neighbors.
> But the network, as a whole, isn't small world, and isn't vulnerable=20
> to vertex-order attacks, right? Or am I missing something?
I believe you are thinking of power-law graphs (also called
"scale-free") which have a few very-high-degree peers that make juicy
targets. Power-law graphs frequently (but don't necessarily) exhibit
small-world characteristics. Almost everyone is connected to some of =
high-degree peers who are all connected together, so there is a lot of
clustering. The high degree peers also provide short-paths everywhere. =
a result, they're small worlds.
However, not all small-worlds are power-law graphs. In particular, DHTs =
not power-law graphs. There are not exceptionally high or low degree =
Daniel Stutzbach Computer Science Ph.D Student
http://www.barsoom.org/~agthorr University of Oregon
p2p-hackers mailing list
p2p-hackers at zgp.org
Here is a web page listing P2P Conferences:
More information about the P2p-hackers